/ BOJ

BOJ_2638_치즈_JAVA

문제 : 치즈

링크 : BOJ_2638_치즈

접근 방식

예전에 풀었던 치즈 문제와 유사한 BFS 문제이다. 치즈에 닿는 겉면을 체크하는 건 이전 문제와 같지만, 치즈가 녹는 조건이 이전과 달리 4방중 2개의 변 이상 공기와 맞닿아 있어야 하는 추가 조건이 생겼다.

그렇기 때문에 기존에 공기에서부터 BFS를 돌려서 맞닿은 면을 바로 없애는 방식은 불가능하게 되었다.

방식을 조금 바꿔서, 0,0. 벽에서부터 시작해서 치즈에 닿을 때마다 카운팅을 한다. 방문한 곳은 다시 이동하지 않게 하면, 카운트 수로 맞닿은 치즈의 면의 개수를 얻을 수 있기 때문에, 카운팅 이후 값이 2이상인 치즈를 녹이면 된다.

따라서 BFS로 카운팅을 하면서 한 번 BFS를 돌린 후 치즈를 일괄적으로 녹이고 시간을 1 증가시키는 방식으로 반복한 후, 치즈가 모두 녹아 없어지는 시간을 출력하도록 한다.

소스 코드

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

public class BOJ_2638_치즈 {

	static int N, M, map[][];
	static int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	static int[][] visited;
	public static void main(String[] args) throws IOException {

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int answer = 0;
		boolean end = true;
		while (end) {
			end = false;
			visited = new int[N][M];
			bfs(0,0);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (visited[i][j] >= 2) {
						map[i][j] = 0;
					}
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] == 1) {
						end = true;
					}
				}
			}

			answer++;
		}

		System.out.println(answer);
	}

	static int bfs(int x, int y) {


		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] { x, y });
		visited[x][y] = 1;

		while (!queue.isEmpty()) {

			int[] temp = queue.poll();

			for (int d = 0; d < 4; d++) {
				int dx = temp[0] + dir[d][0];
				int dy = temp[1] + dir[d][1];
				if(dx < 0 || dx >= N || dy < 0 || dy >= M) {
					continue;
				}

				if (map[dx][dy] == 0 && visited[dx][dy] == 0) {
					queue.offer(new int[] { dx, dy });
					visited[dx][dy] = 1;
				}else if(map[dx][dy] == 1) {
					visited[dx][dy]++;
				}

			}

		}

		return 0;

	}

}

이전에 풀었던 치즈문제와 비슷하면서도 다른 점이 있어 신선했다.