[백준] 2636. 치즈 (Java)

 

문제

2636번: 치즈

 

알고리즘

그래프, 너비우선탐색(BFS), 구현, 시뮬레이션

 

 

풀이

너비우선탐색을 통해 매 시간마다 공기와 접촉한 치즈를 녹이면 된다.

 

판에 가장 자리에는 치즈가 놓여 있지 않는다는 조건이 있으므로

(0, 0) 에서 너비우선탐색을 시작하여 인접한 칸이 공기라면 큐에 넣고, 치즈라면 녹인다.

 

이때, 치즈를 녹여서 공기로 바꾸면 다음 BFS에 영향이 가기 때문에

녹일 치즈의 좌표를 모두 저장했다가 해당 시간의 너비우선탐색이 종료되면 한번에 공기로 바꾼다.

 

녹인 후 남은 치즈 칸 수가 0이 되었다면 해당 시간과 해당 시간에 녹였던 치즈의 칸 수를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

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

		st = new StringTokenizer(br.readLine(), " ");
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int[][] board = new int[R][C];

		int left = 0;
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				left += board[i][j];
			}
		}

		int t = 0;
		while (true) {

			boolean[][] visited = new boolean[R][C];
			ArrayList<Air> removeList = new ArrayList<>();

			ArrayDeque<Air> deque = new ArrayDeque<>();
			deque.add(new Air(0, 0));
			int count = 0;
			while (!deque.isEmpty()) {
				Air cur = deque.poll();

				for (int i = 0; i < dy.length; i++) {
					int ny = cur.y + dy[i];
					int nx = cur.x + dx[i];

					if (ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx])
						continue;

					visited[ny][nx] = true;

					if (board[ny][nx] == 0) {
						deque.add(new Air(ny, nx));
					}

					if (board[ny][nx] == 1) {
						count++;
						removeList.add(new Air(ny, nx));
					}
				}
			}

			left -= count;
			for(Air remove : removeList) {
				board[remove.y][remove.x] = 0;
			}

			if (left == 0) {
				System.out.println(t + 1);
				System.out.println(count);
				return;
			}
			
			t++;
		}
	}

	static class Air {
		int y, x;

		public Air(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}