7576번: 숨바꼭질

문제 풀러가기

7576

설명

토마토가 모두 익을 때까지의 최소 날짜이므로 BFS로 푼다.

코드

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

class Main {
    static int m, n;
    static int[][] box;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1};

    static class Dot {
        int x;
        int y;

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

    public static void bfs(int[][] box, int n, int m) {
        Queue<Dot> que = new LinkedList<Dot>();

        // 익은 토마토 위치 확인
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (box[i][j] == 1) // 해당 위치의 토마토가 익었다면
                    que.offer(new Dot(i, j));
            }
        }

        while(!que.isEmpty()) {
            // 익은 토마토의 위치에서 시작
            Dot dot = que.poll();

            // 상하좌우 한칸씩 확인
            for(int i = 0; i < 4; i++) {
                int nextX = dot.x + dx[i];
                int nextY = dot.y + dy[i];

                // 박스 밖으로 벗어나면
                if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) {
                    continue;
                }

                // 안 익은 토마토인지 확인
                if(box[nextX][nextY] != 0) {
                    continue;
                }

                box[nextX][nextY] = box[dot.x][dot.y] + 1;
                que.offer(new Dot(nextX, nextY));
            }
        }


        int day = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(box[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
                day = Math.max(day, box[i][j]);
            }
        }

        System.out.println(day - 1);
    }

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

        box = new int[n][m];

        for(int i = 0; i < n; i++) {
            str = br.readLine().split(" ");
            for(int j = 0; j < m; j++) {
                box[i][j] = Integer.parseInt(str[j]);
            }
        }

        bfs(box, n, m);
    }
}