백준 2636, 치즈(java)

문제 설명

nxm 칸에 구멍이 있는 치즈가 하나 놓여 있다. 공기와 닿은 칸이 1시간 지나면 녹게 되는데, 치즈의 구멍에는 칸이 없지만 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 이때 치즈가 다 녹는 시간과 마지막 시간에 남은 치즈의 수를 구하여라

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

2636번: 치즈

문제 풀이

언뜻 보면 쉬워 보이지만, 문제를 파악할 때 함정이 있는데 바로 탐색의 중심을 치즈가 아닌 공기로 잡아야 한다는 것이다. 나는 처음에 치즈를 잡아서 공기와 닿은 부분의 조건을 알아내려 했지만, 치즈 안의 구멍까지 고려해야 해서 패턴을 파악하지 못했다. 하지만, 공기를 기준으로 하면 굉장히 쉬워지는 데. 그 이유는 너비 우선 탐색으로 탐색하면서 새로 만든 부분 좌표의 숫자가 1인 경우를 확인해주면 되기 때문이다.

 

이때 조심해야 할 것은 좌표의 숫자가 1이라 공기와 맞닿은 치즈라고 해서 바로 1을 0으로 지우면 안 된다는 점이다. 바로 지워주게 되면 안쪽에 있는 치즈(해당 타임에는 녹지 말아야 할 부분)이 드러나게 되면서 다른 공기 부분과 함께 지워지게 된다. 그러므로 녹는 치즈 칸을 발견해줬으면 2로 표시해서 다 탐색한 후에 지워주면 된다.

 

그리고 계속해서 해당 타임에 지워지는 치즈를 갱신해서 마지막으로 지워지는 치즈를 출력하게 해야 한다.

참고로 findFinish 함수는 map을 확인해서 전부 0이라 치즈가 모두 녹았는지를 확인해주는 메소드이다.

 

import java.util.*;
import java.io.*;

class Pair {
    int row;
    int col;

    Pair (int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {
    public static int rowLength, colLength;
    public static int[][] map;

    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};
    public static boolean[][] visit;


    // 공기를 기준으로
    public static void bfs(int r, int c) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(r, c));

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < rowLength && nC >= 0 && nC < colLength) {
                    if (!visit[nR][nC] && map[nR][nC] == 0) {
                        visit[nR][nC] = true;
                        queue.add(new Pair(nR, nC));
                    } else if(map[nR][nC] == 1) {
                        map[nR][nC] = 2;
                    }
                }
            }
        }
    }

    public static int deleteCheese() {
        int count = 0;
        for (int i=0; i<rowLength; i++) {
            for (int j=0; j<colLength; j++) {
                if (map[i][j] == 2) {
                    map[i][j] = 0;
                    count++;
                }
            }
        }
        return count;
    }

    public static boolean findFinish() {
        for (int i=0; i<rowLength; i++) {
            for (int j=0; j<colLength; j++) {
                if (map[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rowLength  = Integer.parseInt(st.nextToken());
        colLength = Integer.parseInt(st.nextToken());
        map = new int[rowLength][colLength];
        int answer = 0;
        int cheeseCount = 0;

        for (int i=0; i<rowLength; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<colLength; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        while (!findFinish()) {
            answer += 1;
            visit = new boolean[rowLength][colLength];
            bfs(0, 0);

            cheeseCount = deleteCheese();
        }

        System.out.println(answer);
        System.out.println(cheeseCount);

    }

}