[백준] 7576. 토마토

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

7576번: 토마토

https://olsohee.tistory.com/44 이 문제와 마찬가지로 bfs로 탐색하면서 이전 값에 + 1을 해주어 토마토가 익는데 걸리는 일수를 구하면 된다.

 

주의할 점은 우선 처음에 그래프 값을 입력받을 때 익은 토마토의 위치를 큐에 넣어주어야 한다. 그리고 큐에서 토마토의 위치를 빼서 해당 위치의 사방면을 탐색하고, 아직 익지 않은 토마토인 경우 이전 값 + 1을 저장해주면 된다. 그리고 또 다시 큐에 넣으면 된다.

 

포인트는 큐는 선입선출이고, 처음에 그래프 값을 입력받을 때 익은 토마토들의 위치를 먼저 큐에 넣었기 때문에, 이들이 먼저 bfs의 시작점이 된다는 것이다. 그리고 이미 방문해서 이전 값 + 1로 값이 채워진 곳은 중복 방문하지 않기 때문에 "최소" 일수가 저장되는 것이다. 

 

큐가 비면 bfs가 끝난다. 즉 더이상 번질 수 없다는 것이다. 그러면 이제 그래프를 탐색해서 가장 큰 값이 답이 된다. 그러나 만약 익지 않은 토마토가 있다면, 즉 그래프 값이 0이라면 -1을 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;

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

// 시간복잡도: O(V + E)
// = O(n * m + 4V)
// = 1,000,000 + 4,000,000 = 5,000,000
public class Main {

    static int m; // 가로
    static int n; // 세로
    static int[][] map;
    static boolean[][] visited;
    static Queue<Pair> que = new LinkedList<>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    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());
        map = new int[n][m];

        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) {
                    que.offer(new Pair(i, j)); // 익은 토마토들은 큐에 넣어주기
                }
            }
        }

        bfs();

        System.out.println(getResult());
    }

    private static void bfs() {
        // 큐에서 익은 토마토를 꺼내서 하나씩 bfs하기
        while (!que.isEmpty()) {
            Pair p = que.poll();

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

                if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
                    continue;
                }

                // 방문하지 않은 경우(0)만 탐색
                if (map[ny][nx] != 0) {
                    continue;
                }

                map[ny][nx] = map[p.y][p.x] + 1;
                que.add(new Pair(ny, nx));
            }
        }
    }

    private static int getResult() {
        int maxDay = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) { // 익지 않은 토마토가 있으면 -1 출력
                    return -1;
                }
                maxDay = Math.max(maxDay, map[i][j]);
            }
        }
        return maxDay - 1; // 시작점은 날짜에 포함하지 않기 때문에 1을 빼주기
    }

    static class Pair {
        int y, x;

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