[백준(JAVA)] 7576번: 토마토

문제

✔ 난이도 - Gold 5

설명

bfs
multi source. 시작점이 여러곳임

좌표 쭉 돌면서 익은 토마토(1)를 queue에 넣는다
(처음부터 0이 없으면 0을 출력 (다 익어있다) )
그러고 bfs를 돌리면 여러지점에서 동시에 퍼져나가도록 할 수 있음.

다 돌렸는데도 안익은 토마토(0)이 있으면 -1
queue 다 끝났을때의 날짜수가 답임

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] str = br.readLine().split(" ");
        int C = Integer.parseInt(str[0]);
        int R = Integer.parseInt(str[1]);
        int[][] graph = new int[R][C];

        int isAllRiped = 1;
        Queue<int[]> queue = new LinkedList<>();
        
        for (int i = 0; i < R; i++){
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < C; j++){
                graph[i][j] = Integer.parseInt(s[j]);
                if (isAllRiped == 1 && graph[i][j] == 0){
                    isAllRiped = 0;
                }
                if (graph[i][j] == 1){
                    queue.offer(new int[] {i, j, 0});
                }
            }
        }
        // 입력 완료

        if (isAllRiped == 1){
            System.out.println(0);
            return;
        }

        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};

        int day = bfs(graph, queue, dr, dc, R, C);

        for (int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                if (graph[i][j] == 0){
                    System.out.println(-1);
                    return;
                }
            }
        }
        
        System.out.println(day);
    }

    private static int bfs(int[][] graph , Queue<int[]> queue, int[] dr, int[] dc, int R, int C) {
        int day = 0;
        while (!queue.isEmpty()){
            int[] node = queue.poll();
            int cr = node[0];
            int cc = node[1];
            day = node[2];

            for (int i = 0; i < 4; i++){
                int nr = cr + dr[i];
                int nc = cc + dc[i];

                if (nr < 0 || nc < 0 || nr >= R || nc >= C || graph[nr][nc] != 0) continue;

                queue.offer(new int[] {nr, nc, day+1});
                graph[nr][nc] = 1;
            }
        }

        return day;
    }

}

⏰ 시간복잡도

$O(N^2)$