[백준 | Java] 7576 토마토

내 풀이

해당 노드에서부터 상하좌우로 조건에 맞는 경우 계속해서 나아가는 경우로, BFS 알고리즘을 사용했다.

구현 과정은 다음과 같다.

1. 토마토 상태를 나타내는 배열을 받으며 1의 위치는 큐에 삽입
2. 1이나 -1이 들어올 경우 익은 토마토의 개수 +1
3. 익은 토마토의 개수가 전체 토마토의 개수와 같은지 확인 후 같으면 0 반환, 다르면 BFS 연산 진행
4. 큐가 빌 때까지 아래의 과정을 반복
   a. 큐에서 토마토를 하나 꺼냄
   b. 해당 위치에서 상하좌우로 인접한 토마토를 확인
   c. 인접한 위치에 0이 있다면 탐색 진행
   (해당 토마토의 익는 날짜를 현재 날짜 + 1로 설정하여 큐에 추가)
   d. 이전에 익은 토마토의 익는 날짜를 업데이트
5. 0이 남아있다면 -1 출력
6. 모든 토마토가 익었다면 익는 날짜 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int M;
    static int N;
    static int[][] box;
    static boolean[][] visited;
    static int result;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<tomato> queue = new LinkedList<>();
    static int day;

    static class tomato {
        int x;
        int y;
        int day;

        public tomato(int x, int y, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }

    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];
        int ok = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());

                // 익은 토마토 큐에 삽입
                if (box[i][j] == 1)
                    queue.add(new tomato(i, j, 0));

                // 모든 토마토가 익었는지 확인
                if (box[i][j] == 1 || box[i][j] == -1)
                    ok++;
            }
        }

        if (ok == N * M) {  // 모든 토마토가 이미 익어있을 때
            System.out.println(0);
            return;
        }

        bfs();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 방문하지 못한 칸(0이 -1에 둘러쌓여있어 접근하지 못한 경우)이 남아있을 때
                if (box[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        System.out.println(day);
    }

    static void bfs() {
        day = 0;

        while (!queue.isEmpty()) {
            tomato t = queue.poll();
            day = t.day;

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

                if (nx >= 0 && nx < N && ny >= 0 && ny < M && box[nx][ny] == 0) {
                    // 방문한 칸은 1로 바꿔줌(방문 처리)
                    box[nx][ny] = 1;
                    queue.add(new tomato(nx, ny, day + 1));
                }
            }
        }
    }
}