[백준] 7576번 : 토마토

문제

상자에 익은 토마토와 덜 익은 토마토, 빈 공간이 존재할 때

익은 토마토의 주변 한 칸 내에 있는 덜 익은 토마토들은

하루가 지날 때마다 영향을 받아 익는다.

 

이때 상자 안에 존재하는 모든 토마토가 익기 위해서는

최소 며칠이 걸리는지 출력하라. (모두 익을 수 없는 경우에는 -1)

 

접근 방식

익은 토마토가 여러 곳에 존재하는 경우에는 각각의 익은 토마토에서

매일 상하좌우 칸의 덜 익은 토마토를 1로 바꿔줘야 한다.

 

이전에 풀었던 최단 거리 문제와 비슷한 방식으로 풀 수 있는 문제지만

출발지가 여러 개라는 조건이 추가된 문제다.

 

1926번 + 2176번 문제가 합쳐진 경우로

모든 출발지를 찾은 후에 큐에 넣고 BFS 알고리즘을 적용하면서

상하좌우에 거리를 1씩 늘려주면 된다.

 

이번 문제에서 거리는 날짜라고 볼 수 있다는 것이 포인트로

모든 열매가 다 익었을 때의 날짜를 출력하거나

큐를 다 돌았는데도 익지 않은 열매가 존재한다면 -1을 출력하면 된다.

 

풀이

public class Main {

	private static int[] dx = {1, 0, -1, 0};
	private static int[] dy = {0, 1, 0, -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 m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		int[][] tomato = new int[n][m];

		Queue<Pair> queue = new ArrayDeque<>();
		int[][] day = new int[n][m];

		int target = 0;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				int t = Integer.parseInt(st.nextToken());
				tomato[i][j] = t;
				if (t == 1) {
					queue.offer(new Pair(i, j));
					day[i][j] = 1;
				} else if (t == 0) {
					target++;
				}
			}
		}

		if (target == 0) {
			System.out.println(0);
			return;
		}

		while (!queue.isEmpty()) {
			Pair cur = queue.poll();

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

				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (day[nx][ny] > 0 || tomato[nx][ny] == -1) continue;

				target--;
				if (target == 0) {
					System.out.println(day[cur.x][cur.y]);
					return;
				}
				day[nx][ny] = day[cur.x][cur.y] + 1;
				queue.offer(new Pair(nx, ny));
			}

		}

		System.out.println(-1);
	}

	private static class Pair {
		int x;
		int y;

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