문제 출처

단계별로 풀어보기 > 그래프와 순회 > 토마토
https://www.acmicpc.net/problem/7576

문제 설명

익은 토마토, 익지 않은 토마토가 있을 때, 익지 않은 토마토는 익은 토마토에 의해 하루 뒤 익은 토마토가 된다.
익은 토마토를 1, 익지 않은 토마토를 0, 토마토가 없는 칸은 -1이 주어질 때, 토마토들이 전부 익는 최소 일수를 구하라.

접근 방법

토마토의 익은 상태를 나타내는 2차원 배열 arr, 토마토가 익은 일 수를 기록하는 2차원 배열 date들을 통한 bfs로 풀이한다.

익은 토마토는 1개 이상 주어지므로, 익은 토마토들을 시작점으로 먼저 Queue에 삽입하고 bfs를 진행한다.

이 후, 전체 토마토 상자를 순회하며 안익은 토마토가 있는 경우 -1을 출력하고, 아닌 경우 전체 칸에서 가장 큰 수를 출력한다.

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

public class 토마토 {
    static int arr[][];
    static int date[][];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    public static void bfs(){
        Queue<int[]> q = new LinkedList<>();

        for(int y = 0; y < arr.length; y++){
            for (int x = 0; x < arr[0].length; x++){
                if(arr[y][x] == 1){
                    date[y][x] = 0;
                    q.add(new int[]{y,x});
                }
            }
        }

        while(!q.isEmpty()){
            int cur[] = q.poll();
            int cy = cur[0];
            int cx = cur[1];

            for(int i = 0; i < 4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if(nx < 0 || nx >= arr[0].length || ny < 0 || ny >= arr.length) continue;
                if(arr[ny][nx] == -1) continue;

                if(date[ny][nx] == -1) {
                    date[ny][nx] = date[cy][cx] + 1;
                    q.add(new int[]{ny,nx});
                }
            }
        }

    }

    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());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        arr = new int[M][N];
        date= new int[M][N];

        for(int i = 0; i < M; i++){
            Arrays.fill(date[i], -1);
        }

        for(int y = 0; y < M; y++){
            st = new StringTokenizer(br.readLine());
            for(int x = 0; x < N; x++){
                arr[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        bfs();

        int max = 0;
        for(int y = 0; y < M; y++){
            for(int x = 0; x < N; x++){
                if(arr[y][x] == 0 && date[y][x] == -1){
                    bw.write(String.valueOf(-1));
                    bw.flush();
                    bw.close();
                    br.close();
                    return;
                }
                max = Math.max(date[y][x], max);
            }
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음에는 시작점을 전부 Queue에 넣는다는 생각을 하지 못하여, bfs를 진행하면서 date > -1 칸인 경우 현재 date보다 크면 작은 date값으로 바꾼다는 생각을 하고 풀이했었다.

시간 복잡도는 O(N x M)이다.

문제푼 흔적