[BOJ] 토마토 - 7576

🎨 문제

7576번: 토마토

📘 풀이

이 문제는 BFS로 풀 수 있습니다. 익은 토마토를 큐에 넣고 빼면서 주변 토마토를 익은 토마토로 만들어주면 됩니다. 

 

전체 토마토의 개수를 셉니다. 토마토 농장에는 벽이 있습니다. 입력을 받을 때 벽에는 토마토가 없기 때문에 전체 토마토 개수에서 벽 부분은 빼줍니다. 그리고 익은 토마토일 경우 큐에 토마토를 담아 둡니다.

for (int i = 0; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        MAP[i][j] = Integer.parseInt(st.nextToken());
        if (MAP[i][j] == 1) {
            TOMATOS.add(new int[]{i, j});
            VISITED[i][j] = true;
        }
        if (MAP[i][j] == -1) {
            WALL += 1;
        }
    }
}

현재 익은 토마토로 BFS를 하여 다음 번 익은 토마토를 큐에 넣어줍니다. 이 때 몇 번의 사이클이 도는지 계산해야 합니다. 저는 큐가 빌 때까지 도는 while문과 현재 큐에 들어있는 토마토의 개수만큼만 반복하는 for문으로 한 사이클을 돌았습니다.

 

만약 모든 토마토를 익힐 수 없다면 -1을 반환해야 하기 때문에 BFS가 종료되었을 때 익은 토마토의 개수와 BFS의 결과를 비교해 모든 토마토가 익었는지 확인합니다.

private static int bfs() {
    final int[] dR = {0, 0, 1, -1};
    final int[] dC = {1, -1, 0, 0};

    int result = 0;
    int rest = N * M - WALL - TOMATOS.size();
    while (!TOMATOS.isEmpty()) {
        int size = TOMATOS.size();

        for (int i = 0; i < size; i++) {
            int[] cur = TOMATOS.poll();
            int cR = cur[0];
            int cC = cur[1];
            for (int j = 0; j < 4; j++) {
                int nR = cR + dR[j];
                int nC = cC + dC[j];
                if (nR < 0 || nC < 0 || nR >= N || nC >= M) continue;
                if (VISITED[nR][nC]) continue;
                if (MAP[nR][nC] == -1) continue;

                VISITED[nR][nC] = true;
                TOMATOS.add(new int[]{nR, nC});
                rest -= 1;
            }
        }

        result += 1;
    }

    if (rest == 0) return result - 1;

    return -1;
}

📗 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.System.in;

public class Main {

    static int N, M, WALL;
    static int[][] MAP;
    static Queue<int[]> TOMATOS;
    static boolean[][] VISITED;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        N = input[1];
        M = input[0];
        WALL = 0;
        MAP = new int[N][M];
        TOMATOS = new LinkedList<>();
        VISITED = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                MAP[i][j] = Integer.parseInt(st.nextToken());
                if (MAP[i][j] == 1) {
                    TOMATOS.add(new int[]{i, j});
                    VISITED[i][j] = true;
                }
                if (MAP[i][j] == -1) {
                    WALL += 1;
                }
            }
        }
        int answer = bfs();
        System.out.println(answer);
    }

    private static int bfs() {
        final int[] dR = {0, 0, 1, -1};
        final int[] dC = {1, -1, 0, 0};

        int result = 0;
        int rest = N * M - WALL - TOMATOS.size();
        while (!TOMATOS.isEmpty()) {
            int size = TOMATOS.size();

            for (int i = 0; i < size; i++) {
                int[] cur = TOMATOS.poll();
                int cR = cur[0];
                int cC = cur[1];
                for (int j = 0; j < 4; j++) {
                    int nR = cR + dR[j];
                    int nC = cC + dC[j];
                    if (nR < 0 || nC < 0 || nR >= N || nC >= M) continue;
                    if (VISITED[nR][nC]) continue;
                    if (MAP[nR][nC] == -1) continue;

                    VISITED[nR][nC] = true;
                    TOMATOS.add(new int[]{nR, nC});
                    rest -= 1;
                }
            }

            result += 1;
        }

        if (rest == 0) return result - 1;

        return -1;
    }
}