BOJ 7576. 토마토

BOJ 7576. 토마토

풀이

0과 1로 이루어진 2차원 배열이 주어지고, 1은 토마토 0은 익지않은 토마토 -1은 토마토가 들어있지 않은 빈 칸이다.

토마토에서 상하좌우를 탐색해 상하좌우에 있는 칸이 익지않은 토마토라면 거리를 1씩 증가하며 거리를 dist에 저장한다.

주의할 점은 토마토가 여러개 일 수 있다는 점이다.
즉 BFS를 시작할 시작점이 여러개인 것인데
BFS를 시작하기전 토마토가 존재하는 칸(시작점)들을 찾아 먼저 Queue에 넣어준다.

모든 토마토에 대해 탐색을 완료한 후, 가장 긴 거리를 출력하면 된다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int m = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        Queue<int[]> queue = new LinkedList<>();
        int[][] board = new int[n][m];
        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            StringTokenizer s = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int t = Integer.parseInt(s.nextToken());
                board[i][j] = t;
                if (t == 1) queue.offer(new int[]{i, j});
                if (t == 0) dist[i][j] = -1;
            }
        }

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            for (int k = 0; k < 4; k++) {
                int x = p[0] + dx[k];
                int y = p[1] + dy[k];
                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (dist[x][y] >= 0) continue;
                queue.offer(new int[]{x, y});
                dist[x][y] = dist[p[0]][p[1]] + 1;
            }
        }

        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dist[i][j] == -1) {
                    System.out.println(-1);
                    System.exit(0);
                }
                if (max < dist[i][j]) max = dist[i][j];
            }
        }
        System.out.println(max);
    }
}