[Baekjoon Online Judge] 7576번: 토마토

7576번: 토마토

요구사항

 - 창고에는 익은 토마토와 익지 않는 토마토가 있다.
 - 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받는다.
 - 하나의 토마토의 인접한 곳은 상하좌우를 의미한다.
 - 대각선 방향에 토마토는 영향을 받지 않는다.
 - 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.
 - 창고에 모든 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하라.

입력

 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon7576 {

    static int[][] map;
    static int[] xMove = {-1, 1, 0, 0};
    static int[] yMove = {0, 0, -1, 1};
    static int n, m;

    static class Location {
        int x, y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void bfs() {
        Queue<Location> queue = new LinkedList<>();
        int day = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1)
                    queue.add(new Location(i, j));
            }
        }

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            int pollX = location.x;
            int pollY = location.y;

            for (int i = 0; i < 4; i++) {
                int x = pollX + xMove[i];
                int y = pollY + yMove[i];

                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    map[x][y] = map[pollX][pollY] + 1; // 일 수를 더해간다.
                }
            }
            print(); // 디버깅
        }
    }

    public static boolean isLocation(int x, int y) {
        if(x < 0 || x > m - 1 || y < 0 || y > n - 1) return false;
        if(map[x][y] != 0) return false;
        return true;
    }

    public static void print() {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static int getMax() { 
        int max = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == 0) {
                    return -1;
                }
                max = Math.max(max, map[i][j]);
            }
        }
        return max - 1;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        map = new int[m][n];

        for (int i = 0; i < m; i++) {
            String[] s = bufferedReader.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }
        print(); // 디버깅

        bfs();
        bufferedWriter.write(String.valueOf(getMax())); // map에 가장 큰 값을 출력

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 우선 큐에 1이 있는 좌표를 담는다. 하나씩 뽑아가며 주변을 탐방하며 일 수를 늘려가며 값을 채워준다. 0이 아닌 경우는 토마토가 이미 익었거나 없는 경우 이기 때문에 모두 걸러진다.