백준 2636 치즈

https://www.acmicpc.net/problem/2636

소스코드

import java.io.*;
import java.util.*;
public class Main {
	static int R, C;
	static int[][] map;
	static boolean[][] v;
	static List<Point> list;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];	
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}		
		int cnt = 0;
		int remain = 0;
		while(true) {
			list = new ArrayList<Point>();
			v = new boolean[R][C];
			bfs();
			if(list.size() == 0) break;
			remain = list.size();
			cnt++;
		}	
		System.out.println(cnt);
		System.out.println(remain);	
	}
	private static void bfs() {
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(new Point(0, 0));
		v[0][0] = true;
		while(!queue.isEmpty()) {
			Point p = queue.poll();			
			for (int i = 0; i < 4; i++) {
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];			
				// 범위 검사
				if(nr<0 || nc<0 || nr>=R || nc>= C || v[nr][nc]) continue;			
				v[nr][nc] = true;
				// 제일 바깥에서 시작했으니 치즈라면 제일 바깥에 있는 치즈
				if(map[nr][nc] == 1) {
					map[nr][nc] = 0;
					list.add(new Point(nr, nc));
				}				
				// 빈 공간에서 가장 바깥 치즈를 찾아 나간다
				else {
					queue.offer(new Point(nr, nc));
				}
			}
		}
	}
	public static class Point{
		int r, c;
		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}	
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
}

해결방법

외부 공기와 붙어있는 치즈들이 한 시간마다 사라진다. -> 외부 공기를 시작점으로 했을 때 치즈에 도달하면 해당 칸을 0으로 바꾼다. (제일 바깥 테두리는 항상 치즈가 없기 때문에 (0, 0)부터 시작하였다.)

BFS를 한번 돌 때마다 list에 변한 치즈 좌표를 저장하였다. (좌표가 아니라 개수만 저장해도 될듯하다.)

이후 저장된 좌표의 개수가 0이라면 BFS를 그만 돌리고 BFS를 실행한 횟수와 제일 마지막에 저장된 개수를 출력