7576 - 토마토

BFS를 이용해 문제를 풀이했다.

 

dx, dy는 각 좌표로부터 이동할 변화량들을 가진 배열로, 익은 토마토가 다른 토마토들에게 영향을 끼칠 때의 좌표변화를위해 사용했다.

 

각 2차원 배열의 역할은,

tomato -> 해당 토마토가 익었는가? 익었다면 1

map -> 해당 토마토가 익기까지 걸린 시간. 처음부터 익어있었다면 0

이다.

 

해당 문제를 풀다가 실수했었던 점은, "처음부터 익어있었던 토마토들의 좌표를 미리 Queue에 넣어두지 않았던 점"이다.

처음 좌표부터 모든 좌표를 돌며 토마토가 익어있을 경우 BFS를 돌리면, 가장 처음으로 나온 익은 토마토를 기준으로 걸린 시간이 미리 다 정해지기 때문이다.

 

BFS는 어차피 Queue를 이용해 FIFO 형식으로 동작하므로,

Queue

[익은 토마토들의 좌표] -> [익은 토마토들의 좌표, 해당 토마토들에의해 익혀질 토마토의 좌표] (먼저 익은 토마토들부터 처리됨)

와 같이 확장되기 때문에 앞에서부터 뽑아낸다면 각 좌표에 방문하는 순간 항상 최소 시간만에 토마토를 익힐 수 있게된다.

 

package backjoon;
import java.io.*;
import java.util.*;

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

public class P_7576 {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    public static void bfs(Queue<Cords> q, int[][] tomato, int[][] map){
        while (!q.isEmpty()){
            Cords current = q.poll();
            for (int i = 0;i < 4;i++){
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if (nx >= 0 && nx < tomato.length && ny >= 0 && ny < tomato[0].length){
                    if (tomato[nx][ny] == 0 && map[nx][ny] == -1){ // 토마토가 익지 않은 상태
                        q.add(new Cords(nx, ny));
                        map[nx][ny] = map[current.x][current.y] + 1;
                        tomato[nx][ny] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int M = inputs[0];
        int N = inputs[1];
        int[][] tomato = new int[N][M];
        int[][] map = new int[N][M];
        boolean is_finish = true;
        for (int i = 0;i < N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0;j < M;j++){
                tomato[i][j] = Integer.parseInt(st.nextToken());
                map[i][j] = -1;
            }
        }
        Queue<Cords> q = new LinkedList<>();
        for (int i = 0;i < N;i++){
            for (int j = 0;j < M;j++){
                if (tomato[i][j] == 1) {
                    q.add(new Cords(i, j));
                    map[i][j] = 0;
                }
            }
        }
        bfs(q, tomato, map);
        int est_days = 0;
        for (int i = 0;i < N;i++){
            for (int j = 0;j < M ;j++){
                if (tomato[i][j] == 0) {
                    is_finish = false;
                    break ;
                }
                if (map[i][j] > est_days) est_days = map[i][j];
            }
            if (!is_finish) break;
        }
        if (!is_finish) System.out.println(-1);
        else System.out.println(est_days);
    }
}