[BJ]2636. 치즈

BJ G4 2636 치즈

 

 

문제링크

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

2636번: 치즈

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/3VHX8yHFw1Y

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2021/09/15
 * @see https://www.acmicpc.net/problem/2636
 * @git
 * @youtube
 * @performance 12236 92
 * @category #BFS, #DFS, #그래프
 * @note 탐색의 시작을 공기에서하자!
 */

public class BJ_G4_2636_치즈 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int R, C;
    private static int[][] map;
    private static int[][] deltas = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());
        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());

        map = new int[R][C];
        for (int r = 0; r < R; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }
        // 입력 완료
        bfs();
    }

    private static void bfs() {
        // bfs 준비!!
        boolean[][] visited = new boolean[R][C];
        Queue<Point> airs = new LinkedList<>();
        // 초기 설정 - 0,0은 언제나 공기
        visited[0][0] = true;
        airs.offer(new Point(0, 0));

        // 이번에 녹을 치즈 즉 다음 공기 저장
        Queue<Point> newAirs = new LinkedList<>();

        int hour = 0, prev = 0;

        while (true) {
            // bfs로 완탐 --> newAirs 
            while (!airs.isEmpty()) {
                Point head = airs.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = head.r + deltas[d][0];
                    int nc = head.c + deltas[d][1];

                    if (isIn(nr, nc) && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        // 공기면 --> 계속 airs에 넣고 탐색
                        if (map[nr][nc] == 0) {
                            airs.offer(new Point(nr, nc));
                        } else {
                            newAirs.offer(new Point(nr, nc));
                        }
                    }
                }
            }// 1시간 경과.

            // 새로운 공기가 없어졌다면? 종료
            if (newAirs.isEmpty()) {
                break;
            }
            // 새로운 공기가 있다면 한시간 더 동작
            else {
                prev = newAirs.size();
                hour++;

                // 두개의 queue를 swap
                Queue<Point> temp = airs;
                airs = newAirs;
                newAirs = temp;
            }
        }// 전체 반복 종료
        System.out.println(hour);
        System.out.println(prev);
    }

    private static boolean isIn(int r, int c) {
        return 0 <= r && r < R && 0 <= c && c < C;
    }

    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    // REMOVE_START
    private static String src = "13 12\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 1 1 0 0 0\r\n" +
                                "0 1 1 1 0 0 0 1 1 0 0 0\r\n" +
                                "0 1 1 1 1 1 1 0 0 0 0 0\r\n" +
                                "0 1 1 1 1 1 0 1 1 0 0 0\r\n" +
                                "0 1 1 1 1 0 0 1 1 0 0 0\r\n" +
                                "0 0 1 1 0 0 0 1 1 0 0 0\r\n" +
                                "0 0 1 1 1 1 1 1 1 0 0 0\r\n" +
                                "0 0 1 1 1 1 1 1 1 0 0 0\r\n" +
                                "0 0 1 1 1 1 1 1 1 0 0 0\r\n" +
                                "0 0 1 1 1 1 1 1 1 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0";
    // REMOVE_END
}