[백준 7576] 토마토

풀이

 

이 문제는 출력하는 조건을 어떻게 구분할 것인지 고민을 했다.

• 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력
• 토마토가 모두 익지는 못하는 상황이면 -1을 출력
• 토마토가 모두 익을 때까지의 최소 날짜를 출력

처음에는 아래와 같이 설계했다.
- while문을 반복(시간을 1씩 늘려줌)
    - 모든 칸을 탐색하며 안익은 토마토의 개수를 세고, 익은 토마토를 큐에 담는다.
    - 만약, 안 익은 토마토의 개수가 0이라면, (시간-1)을 출력하고 종료.
    - while (큐가 빌때까지)
        - 익은 토마토의 인접한 토마토들을 익게한다.
        - 익은 토마토를 상태 배열에 저장한다.
        - 새롭게 익은 토마토의 개수를 센다.
    - 만약, (안익은 토마토가 있는데 새롭게 익은 토마토의 개수가 0이라면) -1을 출력하고 종료
    - 토마토의 상태를 변경한다.

위와 같이 구현하고 실행했을 때 테스트 케이스는 통과하지만 시간초과가 났다.
그 이유는, 하루가 지날때마다 모든 칸을 탐색하므로 시간초과가 난다.

 

 

그래서 bfs탐색을 하며 익을 수 있는 토마토의 날짜를 box[][]에 저장을 한다.

bfs탐색이 끝나고 box를 탐색하면서

• 안 익은 토마토가 있는 경우, -1으르 출력하고 종료한다.
• 토마토가 익기까지 걸린 날짜중에서 최댓값을 구한다.

(구한 날짜 - 1)을 출력하고 종료한다.

여기서 처음부터 모든 토마토가 익어있는 상태이면 bfs 탐색을 하더라도 안익은 토마토가 없으므로 box[][]의 최대값은 1이다. 그래서 '토마토가 모두 익어있는 상태이면 0을 출력한다'의 조건을 만족하게 된다.

 

어려웠던 부분

 

1. 토마토의 상태를 box에 바로 반영해도 다음 탐색에 영향을 미치지 않을까?
   • 큐가 날짜의 순서를 보장하기 때문에 영향을 미치지 않는다. 그래서 bfs탐색을 하면서 토마토가 익었을 때 바로 box[][]에 반영이 가능하다.

구현

 

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

public class Solution_for_7576 {
    static int M, N;
    static int[][] box;
    static int[][] status;

    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());   // 열
        N = Integer.parseInt(st.nextToken());   // 행

        box = new int[N][M];

        Queue<int[]> queue = new LinkedList<>();

        // 초기 토마토의 상태를 체크
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            for (int m = 0; m < M; m++) {
                box[n][m] = Integer.parseInt(st.nextToken());
                if (box[n][m] == 1) {
                    queue.add(new int[] {n, m});
                }
            }
        }
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            
            for (int d = 0; d < 4; d++) {
                int nextRow = cur[0] + dirs[d][0];
                int nextCol = cur[1] + dirs[d][1];

                if (nextRow < 0 || nextCol < 0 || N <= nextRow || M <= nextCol) continue;

                // 안익은 토마토가 아니라면 탐색할 필요 없음
                if (box[nextRow][nextCol] != 0) continue;

                box[nextRow][nextCol] = box[cur[0]][cur[1]] + 1;
                queue.add(new int[] {nextRow, nextCol});
            }
        }

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