[BOJ 2636] 치즈 (Java)

문제

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

2636번: 치즈

 

풀이

치즈 내부 구멍과 외부 공기 모두 0으로 표시되기 때문에 이를 구분해야 한다. 

 

1. 내부 구멍과 외부 공기를 구분한다.

• 전체 맵의 가장 자리가 비어있기 때문에 첫 번째 좌표 0, 0에서 BFS하여 상하좌우 0인 좌표를 모두 3으로 변경해주었다. 즉, 외부 공기를 3으로 바꿔주었다.

 

아래 단계를 치즈가 사라질 때까지 반복한다.

2. 치즈의 공기 접촉면을 체크한다.

• 맵을 순회하면서 값이 3(외부 공기)일 때, 상하좌우 인접 좌표에 1(치즈)가 있다면 해당 치즈는 공기와 접촉된 치즈임을 알수 있도록 (공기 접촉 치즈) 2로 변경한다. 

 

3. 공기 접촉면을 제외한 내부 치즈 개수를 카운트 한다. 공기 접촉면을 녹인다. 내부에 구멍이 노출된다면 공기로 채워준다.

• 맵에서 1(치즈)의 count를 구한다
• 2(공기 접촉 치즈)를 3(외부 공기)으로 변경한다. (치즈를 녹이는 행위)
• 3(외부 공기)일 경우 상하 좌우 0(내부 구멍)을 체크하여 BFS로 3(외부 공기)으로 변경해준다. 

 

소스코드

package bfs;

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

public class BOJ2636 {

    public static int N, M;
    public static int[][] map;
    public static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int hour = 0;
        int lastCnt = 0;

        map = new int[N][M];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) lastCnt++;
            }
        }
        map[0][0] = 3;
        bfs(0, 0);

        while(true){
            // Boundary -> 2로 바꾸기
            checkBoundary();

            // 남은 치즈 개수 구하기
            // 2 -> 3 으로 바꾸기
            // 3 이면 주변 0 있는지 체크해서 bfs
            int cnt = 0;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(map[i][j] == 1){
                        cnt++;
                    } else if(map[i][j] == 2){
                        map[i][j] = 3;
                    }
                    if(map[i][j] == 3){
                        for(int[] d : dir){
                            int ni = i + d[0];
                            int nj = j + d[1];
                            if(isValid(ni, nj) && isHole(ni, nj)){
                                map[ni][nj] = 3;
                                bfs(ni, nj);
                            }
                        }
                    }
                }
            }
            hour++;
            if(cnt > 0){
                lastCnt = cnt;
            }
            if(cnt == 0) break;
        }

        System.out.println(hour);
        System.out.println(lastCnt);
    }

    public static void checkBoundary(){
        // 3이면 상하좌우 탐색해서 1이면 2로 설정.
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j] == 3){
                    for(int[] d : dir){
                        int ni = i + d[0];
                        int nj = j + d[1];
                        if(isValid(ni, nj) && isCheese(ni, nj)){
                            map[ni][nj] = 2;
                        }
                    }
                }
            }
        }
    }

    public static void bfs(int sx, int sy){
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(sx);
        que.offer(sy);

        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();

            for(int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                if(isValid(nx, ny) && isHole(nx, ny)){
                    map[nx][ny] = 3;
                    que.offer(nx);
                    que.offer(ny);
                }
            }
        }
    }

    public static boolean isValid(int x, int y){
        if(x < 0 || y < 0 || x >= N || y >= M ) return false;
        return true;
    }

    public static boolean isHole(int x, int y){
        if(map[x][y] == 0) return true;
        return false;
    }

    public static boolean isCheese(int x, int y){
        if(map[x][y] == 1) return true;
        return false;
    }
}