백준 2636번 치즈 G4 - BFS

출처 : 나무위키 '테스터 훈'

 

치즈는 위험해..!

 

 

 

문제을 요약하면 1과 0이 맞닿으면 1시간 후, 1이 0이 된다.

모두 사라지는데 걸리는 시간과 사라지기 직전 시간대의 1이 몇개 있는지 출력하면 되는 문제이다.

외각에는 치즈가 없고, 하나 이상의 구멍이 존재하는데 이는 0과 맞닿은것이 아닌걸로 취급한다.

 

결국 치즈의 개수가 0까지 bfs()로 탐색을 지속하고, 외각에서부터 0 주변에 1이 있다면 0으로 바꾸고, 치즈 개수를 줄여주면 되겠다. 또한 한 사이클마다 치즈 개수를 저장하여 다 사라지기 직전 치즈 개수를 남겨주면 되겠다.

 

알고리즘 공부를 입출력이 너무 크지 않는 한 Scanner만 사용했는데

 

BufferedReader, StringTokenizer,  BufferedWriter

 

을 사용해서 풀어보려 한다. 

 

정리: https://hb-in99.tistory.com/91

Java - BufferedReader, StringTokenizer, BufferedWriter

 

 

import java.util.*;
import java.io.*;
 
 
public class Main {// 2636번 치즈 G4
    
    public static int [] dr = {-1,1,0,0};
    public static int [] dc = {0,0,-1,1};
    static int N,M,time,cheese,last_cheese;
    static int [][] arr;
    static boolean[][] visit;
    
    public static  void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        
        for(int i = 0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0; i<N; i++) {
            for(int j = 0; j<M; j++) {
                if(arr[i][j] == 1) {
                    cheese ++;
                }
            }
        }
        
        while(cheese > 0) {
            time ++;
            last_cheese = cheese;
            bfs();            
        }        
        
        bw.write(time+"\n");
        bw.write(last_cheese+"\n");
        bw.flush();
        bw.close();
    }
    
    public static void bfs () {
        Queue <int []> que = new LinkedList<>();
        que.add(new int [] {0,0});
        visit = new boolean[N][M];
        visit[0][0] = true;
        while(!que.isEmpty()) {
            int [] cur = que.poll();
            int now_r = cur[0];
            int now_c = cur[1];
            
            for(int k = 0; k<4; k++) {
                int r = now_r + dr[k];
                int c = now_c + dc[k];
                
                if(!rangechk(r, c))
                    continue;
                if(visit[r][c])
                    continue;
                visit[r][c] = true;
                
                if(arr[r][c] == 1) {
                    arr[r][c] = 0;
                    cheese --;
                }else {
                    que.add(new int [] {r,c});
                }
            }            
        }
    }
    
    public static boolean rangechk(int r, int c) {
        return 0 <= r && 0 <= c && r < N && c < M;
    }
}
 

 

 

치즈 개수를 세고, 0과 접촉한 치즈는 0으로 만들면서 개수를 -- 해줬다.

한 사이클마다 time ++ 을 통해 시간을 체크하고, last_cheese로 치즈 개수를 저장해주어 출력했다.