[문제] 백준 2636번 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

 

내 풀이

 

처음에 치즈 가장자리를 처리하는 방법에 대해 고민을 많이 했다.

치즈가 있는 위치에서 DFS를 하는게 아니라, 외부공기 기준으로 DFS를 해냐가면, 쉽게 가장자리를 처리할 수 있다.

 

public class BOJ_2636 {
	static int[][] matrix;
	static int sero, garo;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		sero = Integer.parseInt(st.nextToken());
		garo = Integer.parseInt(st.nextToken());
		matrix = new int[sero][garo];

		for (int i = 0; i < sero; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < garo; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
//		ArrayList<Integer> list = new ArrayList<>();
		int time = 0;
		int ans = 0;
		while (true) {
			int total = 0;
			boolean[][] visited = new boolean[sero][garo];

			dfs(0, 0, visited);
			total += melt();

//			list.add(total);
			if (total == 0)
				break;
			ans = total;
			time++;

		}
		System.out.println(time);
		System.out.println(ans);
//		for (int i = list.size() - 1; i >= 0; i--) {
//			int a = list.get(i);
//			if (a > 0) {
//				System.out.println(a);
//				break;
//			}
//		}
	}

	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	static void dfs(int r, int c, boolean[][] visited) {

		visited[r][c] = true;

		for (int d = 0; d < 4; d++) {
			int nr = r + dx[d];
			int nc = c + dy[d];
			if (nr < 0 || nc < 0 || nr >= sero || nc >= garo)
				continue;
			if (visited[nr][nc])
				continue;

			if (matrix[nr][nc] == 1)	// 치즈 가장자리 => -1로 처리
				matrix[nr][nc] = -1;
			
			if (matrix[nr][nc] == 0)	// 외부 공기에 대해서만 dfs
				dfs(nr, nc, visited);
		}
	}
	// 치즈 가장자리 (-1로 저장됨) 녹이는 개수 반환 
	static int melt() {
		int ans = 0;
		for (int i = 0; i < sero; i++) {
			for (int j = 0; j < garo; j++) {
				if (matrix[i][j] == -1) {
					ans++;
					matrix[i][j] = 0;	// 공기로 바꿔줌
				}
			}
		}
		return ans;
	}
}