[Baekjoon Online Judge] 2636 - 치즈 / Java

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

2636번: 치즈

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

public class Main {

	// cheeseCnt: 남은 치즈 수
	static int N, M, cheeseCnt;
	static int[][] map;
	static boolean[][] visited;

	// 녹일 치즈 정보 저장
	static Queue<Node> meltList = new LinkedList<>();

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Node {
		int r, c;

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

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		cheeseCnt = 0;

		// map 입력 받기
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());

				// 치즈인 경우
				if (map[i][j] == 1) {
					cheeseCnt++;
				}
			}
		}
		// 이전 시간의 치즈 칸수 저장 변수
		int preCheeseCnt = 0;
		// 지난 시간 저장 변수
		int time = 0;

		while (true) {
			// 녹이기 전 치즈 칸 수 저장
			preCheeseCnt = cheeseCnt;

			// 방문체크 배열 초기화
			visited = new boolean[N][M];
			// 녹일 치즈 목록 초기화
			meltList.clear();
			// 녹일 치즈 칸 탐색
			bfs();

			// 치즈 녹이기
			meltCheese();

			time++;

			// 남은 치즈 개수 0개면 멈추기
			if (cheeseCnt == 0) {
				break;
			}
		}

		System.out.println(time);
		System.out.println(preCheeseCnt);
	}

	private static void bfs() {
		Queue<Node> q = new LinkedList<>();

		visited[0][0] = true;
		q.offer(new Node(0, 0));

		// 녹일 치즈 탐색
		Node n;
		int nr, nc;
		while (!q.isEmpty()) {
			n = q.poll();

			for (int dir = 0; dir < 4; dir++) {
				nr = n.r + dr[dir];
				nc = n.c + dc[dir];

				// 경계 내에 있고 방문하지 않은 경우
				if ((nr >= 0 && nc >= 0 && nr < N && nc < M) && !visited[nr][nc]) {
					// 다음 위치가 공기인 경우
					if (map[nr][nc] == 0) {
						visited[nr][nc] = true;
						q.offer(new Node(nr, nc));
					}
					// 다음 위치가 치즈인 경우
					else {
						// 녹을 치즈 목록에 추가
						meltList.offer(new Node(nr, nc));
					}
				}
			}
		}
	}

	private static void meltCheese() {
		Node n;
		int r, c;

		while (!meltList.isEmpty()) {
			n = meltList.poll();
			r = n.r;
			c = n.c;

			// 아직 녹는 처리 안 된 치즈인 경우
			if (map[r][c] != 0) {
				// 남은 치즈개수 -1, 녹는 처리
				cheeseCnt--;
				map[r][c] = 0;
			}
		}
	}
}