[백준] 7576번 : 토마토 - JAVA [자바]

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

---

bfs 알고리즘 문제이다.

1. 토마토 창고에 대한 정보를 입력받는다.
2. 익은 토마토로 부터 시작한다.
3. 인접한 토마토를 탐색한다. (-1 이 아닌지 (토마토가 없다는 뜻))
4. 인접한 토마토가 0 이면 아직 익지 않은 토마토이다.
5. 하루가 지나야 인접한 토마토가 익을테니까 (현재 토마토가 익은데 걸린 시간 + 1)을 인접한 토마토 창고 위치에 대입해주고 큐에 add 한다.
6. 위의 과정을 반복하여 토마토 창고 배열을 완성하면 배열에서 가장 큰 수 - 1 (처음에 0일이 아닌 1일로 시작했기 때문에) 가 답이 된다.

여기서 의문점이 들 수 있다. 나중의 경우의 수가 날짜가 더 오래 걸리지만 값을 덮어 쓸 수 있지 않는지에 대해서는 이미 배열의 값이 0 아니면 건너뛰기로 했기 때문에 자동으로 걸러진다.

하지만 하나 더 의문점이 든다. 익은 토마토가 여러 개 있을 수 있다. 예를 들어 1 번과 2번 익은 토마토가 있다고 하자. 1번 토마토에 인접하여 익은 3번 토마토가 있다. 3번 토마토는 5일 걸렸다고 하자. 다음으로 2번 토마토에 인접한 토마토들을 익히면서 날짜를 세니 3번 토마토는 3일이 걸렸다. 하지만 이미 3번 토마토 배열에는 5라는 숫자가 있기 때문에 (0이 아니기 때문에) 2번 토마토에 인접하여 익는 경우를 건너뛸 수 있기 때문이다.

이를 방지하기 위해

if (box[newX][newY] == 0) 
-> if (box[newX][newY] == 0 || box[newX][newY] > box[start.x][start.y] + 1)

이렇게 조건문에 추가하여 더 적은 날짜가 걸리면 업데이트 하는 방식으로 할 수 있다.
하지만 이렇게 하면 시간 초과가 발생한다.

이를 해결하기 위해 병렬적으로 bfs를 돌리면 된다.
병렬적으로 돌리면 1번 토마토에서 익는 것과 2번 토마토에서 익는 시간이 같이 돌아가고 3번 토마토에는 더 짧은 날짜인 3일이 이미 입력되기 때문에 1번 토마토에서 익는 경우인 5일이 덮어씌어지는 경우는 발생하지 않는다.

그러면 병렬적으로 bfs 를 어떻게 돌릴까?

이 방법은 매우 간단하다.
처음 토마토 창고 배열을 입력 받을 때 익은 토마토(1)를 큐에 삽입해 주는 것이다.
그러면 bfs 알고리즘 큐에는 1번과 2번 토마토가 들어가고 1번과 인접한 토마토는 날짜가 1일 입력되고 2번 토마토에 인접한 토마토 또한 날짜가 1이 입력되는 것이 병렬적으로 일어난다.

---

public class bj7576 {

    public static int M, N;
    public static int[][] box;
    public static Queue<spot> queue = new LinkedList<>();
    static int[] xMove = {1, -1, 0, 0};
    static int[] yMove = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split2 = line.split(" ");
        M = Integer.parseInt(split2[0]);
        N = Integer.parseInt(split2[1]);

        box = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line1 = br.readLine();
            String[] split = line1.split(" ");
            for (int j = 0; j < M; j++) {
                box[i][j] = Integer.parseInt(split[j]);
                if (box[i][j] == 1) queue.add(new spot(i, j));
            }
        }

        bfs();

        boolean work = true;
        int max = -1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 0) work = false;
                max = Math.max(max, box[i][j]);
            }
        }

        if (work) {
            bw.write((max - 1) + "\n");
        } else {
            bw.write((-1) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs() {
        while (!queue.isEmpty()) {
            spot start = queue.poll();
            for (int i = 0; i < 4; i++) {
                int newX = start.x + xMove[i];
                int newY = start.y + yMove[i];

                if (newX >= 0 && newX < N) {
                    if (newY >= 0 && newY < M) {
                        // 탐색하는 곳에 토마토가 있다면
                        if (box[newX][newY] != -1) {
                            // 그 전의 토마토에서 익는 게 빠른지 이 토마토에서 익는게 빠른지 확인
                            if (box[newX][newY] == 0) {
                                queue.add(new spot(newX, newY));
                                box[newX][newY] = box[start.x][start.y] + 1;
                            }
                        }
                    }
                }
            }

        }
    }

    static class spot {
        int x;
        int y;

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