[정올 2613] 토마토(고) - JAVA

문제 링크

문제 정의

• 토마토가 들어있는 상자가 존재
• 상자는 $N * M$ 개의 칸으로 구성됨ㅁ
• 각 공간에 토마토의 상태에 따라 -1, 0, 1로 구분
  • -1 : 토마토가 없음
  • 0 : 익지 않은 토마토
  • 1 : 익은 토마토
• 상자 안의 익은 토마토는 하루 후 상하좌우로 1칸 반경의 안익은 토마토를 익게함

상자 안의 토마토가 모두 익을 때까지 걸리는 날짜를 출력
상자 안의 토마토가 모두 익지 못한다면 -1를 출력

접근 방법

1. 초기화 - 익은 토마토 찾기

초기화를 하면서 익은 토마토를 찾습니다.
초기 상태에서 상자 안의 익은 토마토가 있는 모든 칸에 대해서 큐에 저장합니다.
익은 토마토는 다음날 상하좌우에 있는 안익은 토마토를 익게하기 떄문에
BFS에 필요한 초기 익은 토마토의 좌표들이 필요합니다.

그렇기 떄문에 입력으로 들어온 좌표의 상태 값이 1인 경우 해당 좌표를 큐에 저장합니다.

2. BFS 수행 (큐 size 이중 while 방법 사용)

최소 시간대를 구하는 문제에서 공간 복잡도를 최소화 하기 위해
이중 while문을 사용해 큐 size 만큼 BFS를 수행하는 방식을 사용했습니다.

이 방법을 사용하면 time별로 BFS 수행을 분리할 수 있고
종료되는 시점이 해당 문제에서 요구하는 값과 같기 때문에 해당 방법을 사용해 구현했습니다.

3. 상자 안의 모든 토마토들이 익었는지 여부 판별

문제에서는 상자 안의 토마토들이 모두 익을 수 있는지 여부를 판별해 정답을 출력하도록 요구하고 있습니다.

그렇기 떄문에 allTomatoesIsRipe라는 메서드를 구현해
BFS 수행 후 상자 안의 모든 토마토가 있었는지를 판별하고
true 시 time을 출력 false 시 -1을 출력하도록 구현했습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;


class Node {
    int y;
    int x;

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

public class Main {
    static StringTokenizer st;
    static int N;
    static int M;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

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

        int[][] grid = new int[N][M];
        ArrayDeque<Node> q = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                if (grid[i][j] == 1) {
                    q.offer(new Node(i, j));
                }
            }
        }


        System.out.println(bfs(grid, q));
    }

    static int bfs(int[][] grid, ArrayDeque<Node> q) {
        int time = 0;
        while(true) {
            int size = q.size();

            while (size-- > 0) {
                Node node = q.poll();
                int y = node.y;
                int x = node.x;

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

                    if (ny < 0 || ny >= N || nx < 0 || nx >= M || grid[ny][nx] != 0) continue;

                    grid[ny][nx] = 1;
                    q.offer(new Node(ny, nx));
                }
            }

            if (q.isEmpty()) break;
            time++;
        }


        return allTomatoesIsRipe(grid) ? time : -1;
    }

    private static boolean allTomatoesIsRipe(int[][] grid) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 0) return false;
            }
        }
        return true;
    }
}