[BOJ] 백준 2636 치즈 (JAVA)

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

2636번: 치즈

 

 

🔍 Solve

BFS를 사용하여 풀었습니다.

문제에서 주의해야 할 점은 공기와 접촉된 치즈는 한 시간이 지나면 녹아 없어지지만, 치즈 안에 있는 구멍에 인접한 치즈는 녹지 않는다는 점이었습니다.

따라서 치즈가 아닌, 공기의 위치를 BFS로 탐색하여 치즈를 녹이는 방법을 선택했습니다.

치즈가 모두 녹기까지 시간이 얼마나 걸렸는지를 배열에 저장하기 위해 기존 공기가 0, 치즈가 1의 값을 가졌던 것을 공기가 1, 치즈가 0의 값을 가지도록 배열에 저장했습니다.

따라서 위 예제의 초기 배열 상태는 아래와 같습니다.

초기 배열을 저장한 뒤 BFS로 그래프를 탐색합니다.

판의 가장자리에는 치즈가 놓여있지 않다고 했으므로 테두리 중 아무 곳이나 시작점을 잡습니다.

저는 (0, 0)부터 배열을 탐색했습니다.

남아있는 치즈의 개수를 저장하는 countCheese변수가 양수라면 bfs탐색을 반복합니다.

bfs가 한번 돌아갈 때마다 몇 시간이 지났는지 저장하는 count변수를 사용하였습니다.

치즈가 모두 녹기 한 시간 전에 남아있는 치즈 조각 개수를 구하기 위해 bfs에는 각 턴마다 녹는 치즈의 개수를 저장하는 meltingCount변수를 사용하였습니다.

 

그래프를 탐색하다 0을 만나면 해당 자리를 count값으로 채워 넣고 visited배열을 통해 방문처리를 합니다.

남아있는 치즈의 개수가 0이 된다면 몇 시간이 지났나 저장하는 변수 count와 마지막 턴에 지워진 치즈의 개수인 meltingCoung를 출력합니다.

 

 

❗ Code

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

public class BOJ_G4_2636_치즈 {
    static int R, C;
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int countCheese;  //남아있는 치즈의 개수
    static int count;  //치즈가 모두 녹아서 없어지는데 걸리는 시간

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];

        for(int i=0;i<R;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++){
                int temp = Integer.parseInt(st.nextToken());
                if(temp==1){
                    map[i][j] = 0;  //치즈 있는 곳
                    countCheese++;
                }else{
                    map[i][j] = 1;  //공기 있는 곳
                }
            }
        }

        //---------------------입력완료------------------------------

        int answer2 = 0;
        int answer1 = 1;
        count = 1;

        while(countCheese>0){
            answer2 = bfs();
            answer1 = count;
            count++;
        }


        sb.append(answer1).append("\n").append(answer2);
        System.out.println(sb);
    }

    static int bfs(){
        Queue<Pos> queue = new LinkedList<>();
        visited = new boolean[R][C];

        queue.add(new Pos(0, 0));
        visited[0][0] = true;

        int meltingCount = 0;  //해당 턴에 지워지는 치즈의 개수

        while(!queue.isEmpty()){
            Pos cur = queue.poll();

            for(int d=0;d<4;d++){
                int nr = cur.r+dr[d];
                int nc = cur.c+dc[d];

                if(isIn(nr,nc) && !visited[nr][nc]){
                    if(map[nr][nc]==0){
                        map[nr][nc] = count;  //해당 위치에 몇 시간이 지났나 저장
                        meltingCount++;  //해당 턴에 지워지는 치즈의 개수 +1
                        visited[nr][nc] = true;  //방문처리
                    }else {
                        visited[nr][nc] = true;  //방문처리
                        queue.add(new Pos(nr, nc));  //위치로 이동
                    }
                }
            }
        }

        countCheese -= meltingCount;  //해당 턴에 지워지는 치즈의 개수만큼 남은 치즈 감소
        return meltingCount;
    }

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

    static class Pos{
        int r;
        int c;

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