[BOJ - Gold V] 토마토 / ⭕

토마토

1. 제출 코드 (31분 26초 / BFS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static class Pos {
        int x, y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static int[][] tomato;
    static ArrayDeque<Pos> good_tomato = new ArrayDeque<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int answer = -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());
        tomato = new int[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                int temp = Integer.parseInt(st.nextToken());
                if(temp == 1) {
                    good_tomato.add(new Pos(i, j));
                }
                tomato[i][j] = temp;
            }
        }
        bfs();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(tomato[i][j] == 0) {
                    answer = -1;
                    break;
                }
            }
            if(answer == -1) break;
        }
        System.out.println(answer);
    }
    public static void bfs() {
        while(!good_tomato.isEmpty()) {
            int size = good_tomato.size();
            for(int i = 0; i < size; i++) {
                Pos t = good_tomato.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = t.x + dx[j];
                    int ny = t.y + dy[j];

                    if (nx >= N || nx < 0 || ny >= M || ny < 0 || tomato[nx][ny] == 1 || tomato[nx][ny] == -1) {
                        continue;
                    }
                    tomato[nx][ny] = 1;
                    good_tomato.add(new Pos(nx, ny));
                }
            }
            answer++;
        }
    }
}

 

2. 구현 로직

• 토마토의 정보를 입력받을 때, 익은 토마토의 정보만을 저장해 놓음으로써 추후 익은 토마토를 찾을 필요가 없게 했다.
• 인접 토마토를 익히기 위해서 BFS를 돌리는데 전에 size를 구하여 현재 익어있는 토마토들만 퍼지게 했다.
• 익은 후에는 answer를 증가시켜 일수를 카운트했다.

1. 토마토의 정보를 배열에 입력하고 익은 토마토는 BFS를 돌릴 계획이라 Queue에 저장했다.
2. 익은 토마토 Queue가 빌 때까지 인접한 상자의 토마토를 탐색하고 익지 않은 토마토는 익도록 값을 1로 변경해준다.
3. 한 사이클이 끝나면 하루가 지난 것이므로 answer를 증가시켜준다.
4. BFS 과정이 끝나면 토마토 상자를 탐색하여 익지 않은 토마토가 있다면 -1을 출력하고 없다면 answer를 출력한다.

3. 유의할 점

• 처음에는 하루가 지날 때마다 토마토 상자를 검증했는데 그럴 필요가 없다는 것을 알았다.