백준 7576: 여러 시작점에서 토마토 BFS 진행하기

백준 7576번: 토마토에서는 시작점이 하나가 아닐 수 있습니다. 익은 토마토가 여러 개라면 각각의 위치에서 동시에 상하좌우로 영향을 줍니다.

익은 토마토를 모두 넣고 시작합니다

입력을 받을 때 익은 토마토의 좌표를 start 리스트에 저장해 두었다가 BFS를 시작할 때 이 좌표들을 모두 큐에 넣습니다. 좌표는 Pos 클래스로 표현했습니다.

문제에서는 첫 입력인 M이 가로, 두 번째 입력인 N이 세로입니다. 아래 코드에서는 첫 입력을 N, 두 번째 입력을 M에 저장했으므로 배열을 map[M][N]으로 만듭니다. 이름만 뒤바뀌었을 뿐 배열의 행과 열을 반대로 만든 것은 아닙니다.

큐에서 꺼낸 위치의 이웃이 아직 익지 않은 토마토인 0이라면, 현재 값에 1을 더해 저장하고 큐에 넣습니다. 이렇게 값을 바꾸면 이미 큐에 넣은 칸을 다시 넣지 않게 됩니다.

탐색이 끝나면 findMax()로 상자 전체를 확인합니다. 0이 하나라도 남아 있으면 모두 익힐 수 없다는 뜻이므로 0을 반환합니다. 그렇지 않으면 가장 큰 값을 반환합니다. 처음부터 익은 토마토를 1로 저장했으므로 최종 출력에서 1을 빼면 각각 -1 또는 실제로 걸린 날짜가 됩니다.

당시 제출 코드

Java

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

class Main {

    static int[][] map;
    static int N, M;
    static Queue<Pos> q = new LinkedList<>();
    static int[] opsX = {-1, 1, 0, 0};
    static int[] opsY = {0, 0, -1, 1};
    static int count;
    static ArrayList<Pos> start = new ArrayList<>();

    static class Pos {
        int x;
        int y;

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


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[M][N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == 1) {
                    count++;
                    start.add(new Pos(i, j));
                }
            }
        }
        bfs();
        bw.write(String.valueOf(findMax() - 1));

        bw.flush();
    }

    public static void bfs() {
        for (Pos pos : start) {
            q.offer(pos);
        }
        while (!q.isEmpty()) {
            Pos node = q.poll();

            for (int i = 0; i < 4; i++) {
                int newX = node.x + opsX[i];
                int newY = node.y + opsY[i];

                if (-1 < newX && newX < M && -1 < newY && newY < N) {
                    if (map[newX][newY] == 0) {
                        q.offer(new Pos(newX, newY));
                        map[newX][newY] = map[node.x][node.y] + 1;
                    }
                }
            }
        }
    }

    public static int findMax() {
        int result = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0) {
                    return 0;
                } else if (map[i][j] > result) {
                    result = map[i][j];
                }
            }
        }
        return result;
    }
}