문제

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

---

입력

• 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M
• 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다.

---

출력

• 출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

---

풀이

제한조건

• (5 ≤ N, M ≤ 100)

접근방법

시뮬레이션, 탐색

시뮬레이션 유형의 문제는 어떤 과정이 반복되는지를 정리하면 간단하게 풀린다.
흐름을 살펴보자면 아래와 같다.

1. 공기의 순환.
2. 치즈가 녹는다.
3. 치즈가 모두 사라졌는가?
	a. 남았다면 1로 이동.
    b. 없어졌다면 종료

이제 각 단계를 어떻게 구현하면 좋을지 생각해보자.
문제에서 특별히 주의할 점은

• 시간 초과
• 중복 연산
  위 2가지 항목의 주의하며 아이디어를 떠올려 보자.

1. 공기의 순환.
치즈 외부의 공기는 동일한 시간(한 번에)에 퍼진다.
따라서 외부 공기의 위치를 저장해두고, BFS를 통해서 확산시킨다.

외부 공기의 위치를 따로 저장하는 이유는 별도로 저장하지 않는다면, 매 시행마다
전체 맵을 순회하기 때문이다.

2. 치즈가 녹는다.
치즈의 위치 또한 별도로 관리하자.
그래야 전체 순회 없이 치즈의 위치를 특정할 수 있다.

각각의 치즈에 대해서 공기와 접촉하여 녹는 치즈인지를 확인한다.
만약 녹는 위치라면 임시로 기록해두자.

모든 치즈에 대해서 한 번 탐색을 하고 난뒤, 녹는 치즈에 대해서 상태값을 변경해주자.
탐색을 수행중에 값을 변경한다면, 변경에 의해 영향을 받아 녹지 않아야 하는 치즈도 녹게된다.

00000
01110
01110
01110
00000

위와 같은 예시에서 (1,1)위치의 치즈가 현재 녹아야 한다.
여기서 (1,1)의 위치를 바로 변경한다면, (1,2)의 치즈를 고려할 때, 인접한 공기가 2칸이 되어 녹아버린다..!

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, M;
	static int[][] arr;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static Queue<int[]> cheese = new ArrayDeque<>();
	static Queue<int[]> air = new ArrayDeque<>();

	final static int AIR = 9;
	final static int CHEESE = 1;
	final static int NO_AIR = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader((System.in)));
		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		M = stoi(inputs[1]);

		arr = new int[N][M];
		for (int i = 0; i < N; ++i) {
			inputs = in.readLine().split(" ");
			for (int j = 0; j < M; ++j) {
				if (i == 0 || j == 0 || i == N - 1 | j == M - 1) {
					arr[i][j] = AIR;
					air.add(new int[] {i, j});
					continue;
				}

				if (CHEESE == stoi(inputs[j])) {
					cheese.add(new int[] {i, j});
					arr[i][j] = CHEESE;
				}
			}
		}

		int time = 0;
		while (!cheese.isEmpty()) {
			airCirculation();
			meltCheese();
			time++;
		}

		System.out.println(time);
	}

	private static void airCirculation() {
		while (!air.isEmpty()) {
			int[] cur = air.poll();

			for (int d = 0; d < 4; ++d) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				if (isInRange(nx, ny) && arr[nx][ny] == NO_AIR) {
					arr[nx][ny] = AIR;
					air.add(new int[] {nx, ny});
				}
			}
		}
	}

	private static void meltCheese() {
		int size = cheese.size();
		List<int[]> list = new ArrayList<>();
		while (size-- > 0) {
			int[] cur = cheese.poll();

			int count = 0;
			for (int d = 0; d < 4; ++d) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				if (isInRange(nx, ny) && arr[nx][ny] == AIR)
					count++;
			}
			if (count >= 2)
				list.add(cur);
			else
				cheese.add(cur);
		}
		for (int[] pos : list) {
			arr[pos[0]][pos[1]] = AIR;
			air.add(pos);
		}
	}

	private static boolean isInRange(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M)
			return true;
		return false;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}