[SWEA]7733번 치즈 도둑(JAVA)

0. 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWrDOdQqRCUDFARG 

SW Expert Academy

 

1. 문제 설명

1) N*N 모양의 치즈에 1~100 까지의 맛있는 정도가 있음

2) X번째 날에 X인 칸의 치즈를 먹는 요정이 100일동안 숨어 있음

3) 100일 중에서 치즈 덩어리가 가장 많을 때의 덩어리 개수 구학히

 

2. 입출력

// input
2
2
1 2
2 1
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

// output
#1 2
#2 5

 

3. 코드

import java.awt.Point;
import java.io.*;
import java.util.*;

public class swea7733 {
	private static int N;
	private static int[][] arr;
	private static boolean[][] visited;
	private static int[] dr = {0, 1, 0, -1};
	private static int[] dc = {1, 0, -1, 0};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			int ans = 0; // 최대 덩어리의 개수
			N = Integer.parseInt(br.readLine()); // 치즈의 한 변의 길이
			arr = new int[N][N]; // 치즈 맛
			int maxDay = 0; // 100일 중 치즈가 다 사라지는 날
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
		
			for(int day = 0; day <= 100; day++) { // 100일 동안
				int temp = 0;
				visited = new boolean[N][N]; // 방문 여부
				for(int i = 0; i < N; i++) {
					for(int j = 0; j < N; j++) {
						if(arr[i][j] > day && !visited[i][j]) {
							visited[i][j] = true;
							dfs(i, j, day);
							temp++;
						}
					}
				}
				ans = Math.max(ans, temp);			
			}
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void dfs(int r, int c, int day) {
		// basis part
		
		// inductive part
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr >= 0 && nr < N && nc >= 0 && nc < N && arr[nr][nc] > day) { // 범위 내에 안 먹은 치즈이면
				if(!visited[nr][nc]) { // 방문 전이면
					visited[nr][nc] = true;
					dfs(nr, nc, day);
				}
			}
		}
	}
}

 

실행 결과

 

4. 회고

1) X번째 일에 X보다 큰 값을 가진 요소를 제외하고 bfs로 탐색 후 치즈 덩어리의 개수를 구함

2) max를 통해 최대 치즈 덩어리의 개수를 구함

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea7733.java