자바(백준) 2636 치즈

오답 노트 & 새로 알게 된 점

처음에 이 문제를 봤을 때, 0과 1을 나누면서 어떻게 처리해줘야 할지 생각을 많이 했다. 

value가 1일 때, 주변에 0이 하나라도 있으면 0이 되고, 

value가 0일 때, 주변에 1인 index를 0으로 만들어준다. 이런 식으로 생각을 했는데, 중앙에 딱 반례가 바로 생기는 것이다. value가 0일 때, 주변에 1이 있는데 1시간 뒤에 녹지 않고 있다. 그래서 계속 어떻게 풀어야 할지 고민을 했다. 

그래서 0,0부터 시작해서 bfs를 사용하여 제일 바깥 쪽 공기를 -1로 만들어준 다음, -1을 만난 1만 0으로 바꾸려고 했다. 그러나 뭔가 안될 것 같아 하지 않았다. 그래서 하루정도 생각을 했다. 그래도 문제가 풀리지 않아 힌트를 보았다. 힌트를 보니 두 번째 생각과 비슷한 맥락이었다. 그러나 -1로 바꾸지 않고 그냥 bfs를 돌린 것이다. 그 대신에 bfs를 한 번 돌려서가 아니라 cheese가 다 없어질 때까지였다. 코드 주석을 보고 이해하자

 

그리고 bfs를 공부할 때, 무조건 뭐 특정한 수 만났다해서 바로 q에 넣지 말고, 이게 q에 넣어도 될 건지 아닐 건지도 생각해보자. 이 문제에서는 bfs를 할 때 무조건 큐에 떄려박으니까 이런 문제가 나온 것 같다. 그래서 해당 문제를 풀고 난 느낀 점은 일단 큐에 다 때려 박지 말자. 뭐를 때려박을지 생각을 하자. 여기선 1을 넣을 건지 0을 넣을 건지 말이다.

 

일단 이런 문제를 볼 때는, 내가 맞다고 생각하고 구현을 끝까지해보자. 시간 아깝다 생각하지 말고, 끝까지 도전해서 풀어보자. 아니면 어쩌겠느냐 처음부터 다시 풀어야지. 이러한 시간들이 모두 나에게 득이 된다고 생각하자. 물론 학교 공부도 중요하지만 이것도 나름 중요하다. 우선순위를 두고 공부하자. 

 

---

package BFS;
 
import java.util.*;
import java.io.*;
 
 
public class Main {
    static int row, col, cheese = 0, depth = 0, result;
    static int arr[][];
    static boolean visit[][];
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,1,-1};
    public static void main(String[] args) throws IOException{
        //이 코드를 보고 이해가 안가면 무조건 예제 그림을 손으로 하나씩
        //언제 q에 offer하고 poll하는지 체크해가면서 해야한다.
        //나도 하나하나 다 손으로 해본 뒤 이해가 갔다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
 
        arr = new int[row][col];
 
        for(int i = 0; i < row; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < col; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1) cheese++;
            }
        }
 
        //치즈가 다 없어질 때까지 bfs를 돌린다.
        while(cheese != 0){
            depth++;
            //난 이 아래 부분이 정말 중요하다고 생각함.
            //왜냐하면 문제에서 치즈가 모두 없어지기 한 시간전에 치즈가 몇 개있는지 물어보는거임.
            //만약에 bfs를 돌리고 나서 치즈가 다 없으면 반복문이 끝나게 됨.
            //따라서 지금 이렇게 저장한 이유는 bfs를 돌리기 전의 치즈의 값을 저장함으로써
            //다른 조치를 취하지 않고 치즈가 모두 없어지기 1시간 전의 개수를 구할 수 있음
            result = cheese;
            bfs();
        }
        System.out.println(depth);
        System.out.println(result);
 
    }
    static void bfs(){
        Queue<CheesePoint> q = new ArrayDeque<>();
 
        visit = new boolean[row][col];
        q.offer(new CheesePoint(0, 0));
        visit[0][0] = true;
        while(!q.isEmpty()){
            CheesePoint cp = q.poll();
            for(int i = 0; i < 4; i++){
                int X = cp.x + dx[i];
                int Y = cp.y + dy[i];
                if(!isRangeTrue(X, Y)) continue;
                if(visit[X][Y]) continue;
 
                //0이면 그대로 q에 넣어줌
                if(arr[X][Y] == 0){
                    q.offer(new CheesePoint(X, Y));
                    visit[X][Y] = true;
                }
                //1이면 0으로 바꿔준 뒤 치즈를 하나 없앰
                else if(arr[X][Y] == 1){
                    arr[X][Y] = 0;
                    cheese--;
                    visit[X][Y] = true;
                }
            }
        }
    }
    static boolean isRangeTrue(int x, int y){
        return x >= 0 && x < row && y >= 0 && y < col;
    }
}
 
class CheesePoint{
    int x, y;
 
    CheesePoint(int x, int y){
        this.x = x;
        this.y = y;
    }
}