[BOJ] 백준 2638 치즈 (JAVA)

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

2638번: 치즈

 

🔍 Solve

해당 문제와 패키지인 골드5 2636 치즈와 같이 풀어보면 좋은 문제입니다.

2636 치즈문제는 아래 포스팅을 참고하시면 좋을 것 같습니다!

2022.03.30 - [알고리즘/백준] - [BOJ] 백준 2636 치즈 (JAVA)

[BOJ] 백준 2636 치즈 (JAVA)

 

2636문제와 이 문제 모두 공기를 기준으로 bfs탐색을 하면 되는 문제이지만, 다른 점은 이 문제는 각 치즈 격자의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉해야 치즈가 녹아 없어지는 점입니다.

 

따라서 이 문제에서 가장 중요한 포인트는, 치즈를 바로 녹이지 않고, 해당 턴이 다 돈 후! 그때 모아서 한 번에 지우는 것입니다!!

치즈를 바로 지우지 않는 이유는, 만약 앞의 치즈가 먼저 지워져 0(공기)이 되었으면, 다음 치즈를 탐색할 때 영향을 주기 때문입니다.

 

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다고 했으므로, (0,0) 또는 다른 테두리 지점에서부터 bfs를 탐색할 수 있습니다. 

입력받을 때부터 치즈의 개수를 세어주어 countCheese 변수에 저장합니다.

while문을 통해 치즈의 개수가 남아있다면 bfs탐색을 반복합니다.

 

bfs에서는 다음 위치가 치즈라면 치즈를 바로 녹이지 않고, 해당 map배열을 1 증가시켜줍니다.

bfs를 한 턴 다 돌았다면 map배열을 전체 탐색합니다.

map배열에 3 이상의 값이 저장되어 있다면, 2면 이상이 공기와 접촉된 치즈 위치 이므로, 치즈의 개수를 감소시키고, 공기(0)로 초기화합니다.

1이나 2의 값으로 녹지 않고 남아있는 치즈는 다음 턴에 영향이 없도록 다시 치즈(1)로 초기화 합니다.

 

해당 문제와 비슷하게, bfs를 탐색하며 모아두었다 한 번에 지우는 문제로 다음 문제도 풀어보시면 좋을 것 같습니다.

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

2573번: 빙산

 

❗ 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 Main {
    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 day;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        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());
                map[i][j] = temp;
                if(temp==1) countCheese++;  //초기 치즈 개수 세기
            }
        }

        while(countCheese>0){ //치즈 남았으면 반복
            day++;
            bfs();
        }

        System.out.println(day);

    }

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

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


        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)) continue;
                if(visited[nr][nc]) continue;
                if(map[nr][nc]!=0){  //다음 위치가 치즈라면
                    map[nr][nc]++;  //치즈 위치 값 -1
                }else{
                    visited[nr][nc] = true;
                    queue.add(new Pos(nr, nc)); //다음 위치가 공기라면 위치이동
                }
            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j]==1 || map[i][j]==2){  //1이거나 2여서 녹지 않은 것들은
                    map[i][j] = 1;  //다음 턴 영향 없게 다시 치즈값인 1로 초기화
                }
                if(map[i][j]>=3){  //3이상인 곳에선
                    countCheese--;  //치즈 녹이고
                    map[i][j] = 0;  //공기로 초기화
                }
            }
        }

    }

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

    private static class Pos{
        int r;
        int c;

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