[백준] 2636 치즈 (Java)

[2636 치즈]

난이도: 골드4

2636번: 치즈

문제

입력

출력

---

[아이디어]

이 문제는 BFS를 사용하면 된다고 바로 감이 올 것이다. 하지만 어려운 부분은 어떻게 외부 공기가 닿는 부분만 체크를 하는가이다. 문제를 해결하는 방법은 거꾸로 생각하기이다. 보통 치즈를 너비 우선 탐색하는 방법을 사용하지만, 이 문제는 바깥의 공기를 너비 우선 탐색하여 체크해주는 것이 포인트이다.

 

먼저 바깥의 공기를 너비 우선 탐색해서 어느 부분이 공기인지 체크해준다. 그 후 전체를 탐색하면서 치즈인 경우 아까 탐색한 공기와 닿아있는지를 체크해주면 된다.

 

막상 아이디어대로 문제를 풀면 어렵지 않지만, 결국 이 방법을 생각해지 못해서 나는 다른 사람의 아이디어를 본 후에 풀 수 있었다.

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M;
	static boolean [][] cheezes;
	static boolean [][] visited;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	static Queue<Point> Q = new LinkedList<>();
	
	static class Point {
		int r, c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		cheezes = new boolean [N][M];
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < M; c++) {
				if(Integer.parseInt(tokens.nextToken()) == 1) cheezes[r][c] = true;
			}
		}
		
		int time = 0;
		int lastCnt = 0;
		while(true) {
			visited = new boolean [N][M];
			time++;
						
			// 바깥의 공기들을 체크해주기
			Q.offer(new Point(0, 0));
			visited[0][0] = true; // 공기라면 true
			
			while(!Q.isEmpty()) {
				Point now = Q.poll();
				
				for(int i = 0; i < 4; i++) {
					int nr = now.r + dr[i];
					int nc = now.c + dc[i];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc] || cheezes[nr][nc]) continue;
					
					Q.offer(new Point(nr, nc));
					visited[nr][nc] = true;
				}
			}
			
			int cheeze = 0; // 공기와 닿은 치즈 개수
			for(int r = 1; r < N - 1; r++) {
				for(int c = 1; c < M - 1; c++) {
					if(!cheezes[r][c]) continue;
					
					int cnt = 0;
					for(int i = 0; i < 4; i++) {
						int nr = r + dr[i];
						int nc = c + dc[i];
						
						// 공기와 닿은 경우
						if(visited[nr][nc]) cnt++;
					}
					
					if(cnt > 0) {
						cheeze++;
						cheezes[r][c] = false;
					}
				}
			}
			
			if(cheeze == 0) break;
			lastCnt = cheeze;
		}
		
		System.out.println(time - 1);
		System.out.println(lastCnt);

	}

}