[Algorithm/Java] 백준 7576 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

풀이

하루가 지날 때마다 익은 토마토 상하좌우에 있는 익지 않은 토마토들이 익게 된다. 이렇게 토마토들이 익어가는 과정을 BFS(너비우선탐색)을 통해 해결할 수 있다.

소스코드

public class BOJ_G5_7576_토마토 {

	static int N, M, box[][], MIN;
	static int[] dr = { -1, 1, 0, 0 }; // 4방탐색 시 변하는 row값
	static int[] dc = { 0, 0, -1, 1 }; // 4방탐색 시 변하는 column값

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		List<Integer[]> tomato = new ArrayList<>();
		MIN = Integer.MAX_VALUE;
		box = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == 1) {
					tomato.add(new Integer[] { i, j });
				}
			}
		}
        
		int[][] days = new int[N][M]; // 토마토가 익는 일수들을 저장하는 배열
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				days[r][c] = -1;
			}
		}
        // BFS 탐색 시작
		Queue<Integer[]> Q = new LinkedList<>();
		for (int i = 0, size = tomato.size(); i < size; i++) {
			int startR = tomato.get(i)[0];
			int startC = tomato.get(i)[1];
			Q.offer(new Integer[] { startR, startC, 0 });
			days[startR][startC] = 0;
		}

		while (!Q.isEmpty()) {
			Integer[] cur = Q.poll(); // cur[0] : row, cur[1] : column, cur[2] : 토마토가 익는데 걸린 days
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];

				if (nr < 0 || nc < 0 || nr >= N || nc >= M) // 범위에 벗어난 경우
					continue;
				if (days[nr][nc] != -1 || box[nr][nc] != 0) // 이미 방문했거나 익지 않은 토마토가 없는 경우
					continue;
				if (box[nr][nc] == 0) { // 익지 않은 토마토인 경우
					days[nr][nc] = cur[2] + 1;
					Q.offer(new Integer[] { nr, nc, cur[2] + 1 });
				}
			}
		}
		int max = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (days[r][c] == -1 && box[r][c] == 0) {
					System.out.println(-1);
					return;
				}
				max = Math.max(days[r][c], max);
			}
		}

		if (max < MIN) {
			MIN = max;
		}

		System.out.println(MIN);

	}

}