백준] 2636 치즈

 

KeyPoint!

한번에 다 녹는 경우! 를 생각하지 못해서 틀렸었다..ㅠ_ㅠ...

BFS로 배열을 탐색하면서 0과 인접해있는 1에 대해서는 녹이면서 진행하였다.

BFS돌리면서 0과 인접해있는 1 (= 녹일 치즈)에 대해서는 queue에 넣지 않고, 나머지 0에 대해서는 queue에 넣었다.

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

/*
 * keyPoint!!
 * 
 * 한번에 다 녹는 경우를 생각하지 못했다.
 * 그래서 한번에 다 녹는 테케의 경우 치즈의 개수가 0개가 나와서 틀렸었다.
 */
public class Main {

	static boolean[][] visited;
	static int[][] map;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int R, C, cheeseCnt, time;

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		visited = new boolean[R][C];
		int tmp = 0;
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					tmp++;
				}
			}
		}
		// --------------------입력부

		while (true) {
			bfs();
			time++;

			boolean flag = true;
			cheeseCnt = 0;
			for (int i = 0; i < R; i++) { // 모든 치즈가 다 녹았는지 파악
				for (int j = 0; j < C; j++) {
					if (map[i][j] != 0) {
						flag = false;
						cheeseCnt++;
					}
				}
			}
			
			if (flag) //모든 치즈가 다 녹았다면
				break;
			
			visited = new boolean[R][C];
			tmp = cheeseCnt;
		}

		System.out.println(time);
		System.out.println(tmp);
	}
    
    // 치즈를 녹이는 함수
	public static void bfs() { 
		Queue<dot> qu = new LinkedList<>();
		qu.add(new dot(0, 0));

		dot dot;
		while (!qu.isEmpty()) {
			dot = qu.poll();
			for (int i = 0; i < 4; i++) {
				int nr = dot.r + dr[i];
				int nc = dot.c + dc[i];

				if (nr >= 0 && nr < R && nc >= 0 && nc < C && !visited[nr][nc]) {
					if (map[nr][nc] == 0) { 
						qu.add(new dot(nr, nc));
						visited[nr][nc] = true;
					} else { // 0이 아니면 1이다. 1인부분은 공기랑 닿아있는 1인부분이니까 
						map[nr][nc] = 0; //녹아 없어지게 만들자!
						visited[nr][nc] = true;
					}
				}
			}
		}
	}

	static class dot {
		int r;
		int c;

		public dot(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
}