백준 2636 - 치즈 - BFS

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

2636번: 치즈

 

랭크 : 골드 4

걸린 시간: 40분

 

 

해설

 

이 문제는 치즈가 시간이 지날 때마다 공기와 닿는 부분이 녹는 문제이다. 

 

쉽게 생각하면 자칫 할 수 있는 오류는 다음과 같다. 

"공기를 queue에 담은 후 BFS를 진행하면서 시간(== 닿는데 걸린 거리)을 체크하면 되지 않을까? "

 

이러한 점은 문제가 다음과 같다. 

1. 치즈 안의 공기, 즉 가장 자리와 맞닿아 있지 않은 공기는 치즈를 녹이지 않는다.

2. 새로 생긴 구멍에 의해서 접한 치즈가 공기와 닿아서 녹는 경우를 처리하지 못한다. 

 

아이디어를 생각해보면 다음과 같은 논리를 생각해볼 수 있다. 

1.'가장 자리'에 해당하는 노드들 (치즈 하나가 담긴 칸을 노드라 하겠다. ) 을 모두 queue에 넣은 후, 4방향으로 딱 한번씩 접근해보면, 녹을 치즈들을 모두 만날 수 있다. 

2. 한번 녹은 치즈는, 해당 노드는 자기 역시 '가장자리'로 변하고 (가장자리에 의해서 녹았기 때문에 반드시 가장자리와 맞닿아 있다. ) 다음 가장자리의 후보가 된다. 

3. 1과정에서 '가장 자리'에 해당하는 노드를 모두 queue에 넣는 방법은, queue1에 가장 자리에 해당하는 일부 노드를 넣은 후 BFS를 통해 queue2에 모두 넣는 과정을 수행하는 방법이 있다. 

4. queue2에 만약 모든 가장자리 노드가 있다면, 1 과정을 queue2를 이용해서 수행하면 된다.

5. 1 과정에 의해서 녹은 치즈들을 만날 때마다, 해당 치즈는 2에 해당하는 '가장 자리 후보' 이므로 3과정의 queue1에 넣으면 된다 .

 

 

 

따라서 bfs, queue 를 각각 2개씩 사용하면 된다.

 

bfs1 : queue1 사용, queue1에는 일부 공기들이 들어있다주위 공기들을 모두 순회하면서 queue2에 넣는다. (자기 자신 포함) 

(단, 이 공기로 인해 모든 주위 공기를 순회할 수 있다. -> 문제에서 가장자리는 모두 공기이기 떄문에 4개 꼭짓점으로 시작하면 됨. 이후에는 queue2에서 만난 치즈를 넣어주면 됨. ) 

bfs2 : queue2 사용, queue2에는 모든 가장자리가 들어있고, 4방향으로 한칸씩만 탐색해서 치즈를 만날 경우 공기로 바꿔주고, 이 칸이 공기가 되므로 queue1에 다시 넣어준다. 

 

 

코드

구현한 코드는 다음과 같다. 

설명한 queue1이 코드 상의 airQueue, queue2가 queue에 해당한다. 

설명한 bfs1이 bfsForEdge이고, bfs가 BFS 에 해당한다. 

 

import java.io.*;
import java.util.*;

public class BOJ2636_치즈 {
    static int N, M;
    static int []dy = {-1, 0, 0, 1};
    static int []dx = {0, -1, 1, 0};

    static int [][]board;
    static int [][]visited;
    static int [][]time;
    static int timeCur = 1;
    static Queue<Pair> queue = new ArrayDeque<>();
    static Queue<Pair> airQueue = new ArrayDeque<>();
    static final int AIR = 10;

    static class Pair {
        int r;
        int c;

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

    public static boolean canGo(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < M;
    }

    public static boolean BFS() {
      
        if(queue.isEmpty())
            return false;

        while(!queue.isEmpty()) {
            Pair cur = queue.poll();
            // System.out.println("current : " + cur.r + " "  + cur.c);

            for(int i = 0; i < 4; i++) {
                int nextr = cur.r + dy[i];
                int nextc = cur.c + dx[i];

                if(canGo(nextr , nextc) && visited[nextr][nextc] != AIR){
                    visited[nextr][nextc] = AIR;
                    if(board[nextr][nextc] == 1) {
                        time[nextr][nextc] = timeCur;
                        airQueue.offer(new Pair(nextr, nextc));
                    }
                }
            }

        }
        return true;
    }

    public static void bfsForEdge(){ //바깥 공기에 해당하게 된 노드들을 가지고 공기를 visited에 표시, 그리고 다음 bfs 큐에 삽입
     
        while(!airQueue.isEmpty()){
            Pair cur = airQueue.poll();

            queue.offer(new Pair(cur.r, cur.c));
            for(int i = 0; i < 4; i++) {
                int nextr = cur.r + dy[i];
                int nextc = cur.c + dx[i];

                if(canGo(nextr , nextc) && visited[nextr][nextc] != AIR && board[nextr][nextc] == 0){
                    visited[nextr][nextc] = AIR;
                    airQueue.offer(new Pair(nextr, nextc));
                    queue.offer(new Pair(nextr, nextc));
                }
             
            }
        }
    }

    public static void printVisit(){
         System.out.println("visited");
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++) {
                System.out.print(visited[i][j]  + " ");
            }
            System.out.println();
        }
        System.out.println();
    }


    public static void printTime(){
        System.out.println("time");
       for(int i = 0; i < N; i++){
           for(int j = 0; j < M; j++) {
               System.out.print(time[i][j]  + " ");
           }
           System.out.println();
       }
       System.out.println();
   }
    
    public static void main(String []args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int []input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = input[0];
        M = input[1];


        board = new int[N][];
        visited = new int[N][M];
        time = new int[N][M];
        for(int i = 0; i < N; i++) {
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        airQueue.offer(new Pair(0,0));
        airQueue.offer(new Pair(0, M -1));
        airQueue.offer(new Pair(N-1, 0));
        airQueue.offer(new Pair(N - 1, M -1));

        while(true){
            bfsForEdge();
            boolean result = BFS();
            timeCur++;
            if(!result)
                break;
        }
        
        int maxTime = -1;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++){
                maxTime = Math.max(maxTime, time[i][j]);
            }
        }

        int count = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++){
                if(time[i][j] == maxTime)
                    count++;
            }
        }
        System.out.println(maxTime);
        System.out.println(count);
    }
}