[백준 7576번] 토마토

문제 링크: 7576번 토마토

https://www.acmicpc.net/problem/7576

 

먼저 상자 전체를 순차적으로 탐색하면서 익은 토마토의 위치를 큐에 저장한다. 그 이후에 큐가 빌 때까지 BFS를 바로 수행해준다.

BFS를 끝마친 후 마지막에 익지 않은 토마토를 찾았을 때, for문을 일일이 탈출하지 말고 label을 이용하면 보다 편리하다.

 

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

public class Main {
    static int[][] tomato;
    static int[] drow = {0, 0, 1, -1}; // 동서남북
    static int[] dcol = {1, -1, 0, 0}; // 동서남북
    static int m;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] mn = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        m = mn[0];
        n = mn[1];
        tomato = new int[n][m];

        Queue<Integer[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < m; j++) {
                int cur = temp[j];
                tomato[i][j] = cur;
                if (cur == 1)
                    queue.offer(new Integer[]{i, j});
            }
        }

        while (!queue.isEmpty()) {
            Integer[] cur = queue.poll();
            int row = cur[0];
            int col = cur[1];

            for (int d = 0; d < 4; d++) {
                int nrow = row + drow[d];
                int ncol = col + dcol[d];
                if (nrow<0 || ncol<0 || nrow>=n || ncol>=m || tomato[nrow][ncol] != 0) continue;

                // visit
                tomato[nrow][ncol] = tomato[row][col] + 1;

                // offer to queue
                queue.offer(new Integer[]{nrow, ncol});
            }
        }

        int max = 0;
        boolean flag = false;
        outer:
        for (int i=0; i<n; i++) {
            for (int j =0; j<m; j++) {
                if (tomato[i][j] == 0) {
                    flag = true;
                    break outer;
                }
                if (tomato[i][j] > max)
                    max = tomato[i][j];
            }
        }

        if (flag) System.out.println(-1);
        else System.out.println(max-1);
    }
}