[백준] 2636 치즈 (JAVA)

문제 링크:

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

 

 

문제:

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

 

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

 

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

 

입력:

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

 

 

출력:

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

문제 이해:

이 문제는 치즈가 공기와 맞닿으면 한 시간 뒤 녹아 사라진다는 조건을 바탕으로 한다.

즉, 공기(0)에 접한 치즈(1)는 한 시간이 지나면 없어지며, 이 과정을 반복해 치즈가 모두 사라질 때까지의 걸린 시간과 마지막으로 남아있던 치즈의 개수를 구하는 것이 목표다.

 

그림 1은 원래의 치즈 상태를 보여준다. 가장자리에 있는 치즈들이 외부 공기와 접촉하고 있기 때문에, 한 시간 후 이 치즈들은 녹아 사라진다.

그 결과가 그림 2이며, 'c'로 표시된 부분이 사라진 영역이다.

 

그림 2에서도 마찬가지로, 가장자리에 남아 있던 치즈들이 외부 공기와 접촉하게 되어 한 시간 후 사라지고, 그 결과가 그림 3이다.

그림 3 이후에는 더 이상 치즈가 남아 있지 않으므로 시뮬레이션은 종료된다.

 

이 시점은 3시간 경과 후이고, 그 직전(2시간 시점)에는 치즈가 5개 남아 있었다.

따라서 예제 출력은 3 5가 된다.

 

 

구현 방향:

이 문제를 해결하기 위해서는 탐색 알고리즘, 특히 BFS를 활용하게 된다.

처음에는 치즈(1)를 중심으로 BFS를 수행하며, 외부 공기와 맞닿은 치즈를 찾아 0으로 바꾸는 방식으로 접근했다. 하지만 이 방식에는 어려움이 있었다.

문제는 치즈 내부에 갇힌 공기(0)도 존재한다는 점이다.
이 내부 공기는 외부와 닿아 있지 않음에도 단순히 0이라는 이유로 탐색 대상이 되어버리기 때문에, 진짜 외곽 치즈만 구별하기가 쉽지 않다.

 

그래서 접근 방식을 바꾸었다.

치즈가 아닌 외부 공기(0)를 기준으로 BFS를 시작해, 공기와 맞닿아 있는 치즈를 탐색하는 방식이다.
이렇게 하면 외부 공기에 노출된 치즈만 자연스럽게 식별할 수 있다.

구현의 핵심은 다음과 같다:

• BFS를 통해 외부 공기(0)에서 출발한다.
• 인접한 칸이 치즈(1)인 경우, 해당 칸을 임시값 2로 변경해 표시한다.
  → 이때 바로 0으로 바꿔버리면, 현재 순회 도중 즉시 공기가 되어버려 다음 탐색 결과에 영향을 주기 때문에 주의가 필요하다.
• 한 시간 단위의 순회가 끝난 뒤, 치즈(2)를 모두 0으로 바꾸고 치즈 개수를 갱신한다.

이 과정을 반복하다 보면 치즈가 모두 사라지는 시점을 알 수 있고,
마지막으로 치즈가 존재했던 시점의 개수도 함께 기록할 수 있다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

정답 코드:

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 N,M;
    static int[][] matrix;
    static boolean[][] visited;
    static int totalTime=-1;
    static int lastCheeseCount=0;
    static boolean over; // 남은 치즈가 없다면 끝

    public static void bfs(int x, int y) {
        int count=0; //테두리 부분 카운트
        visited[x][y]=true;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x,y});

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x1 = curr[0];
            int y1 = curr[1];
            ////////////녹일 치즈가 있는지 확인////////////////
            //상 (위에 치즈가 있는 경우)
            if(x1>0&& matrix[x1-1][y1] ==1){
                matrix[x1-1][y1]=2; //녹인 부분 2로 표시
            }

            //하
            if(x1+1<matrix.length && matrix[x1+1][y1]==1){
                matrix[x1+1][y1]=2;
            }
            //좌
            if(y1>0 && matrix[x1][y1-1]==1) {
                matrix[x1][y1-1]=2;
            }
            //우
            if(y1+1<matrix[0].length && matrix[x1][y1+1]==1){
                matrix[x1][y1+1]=2;
            }

            /// ////////////////////////////////////////////////////
            /// ///////////////// 0부분 모두 탐색 시작/////////////////
            //상
            if(x1>0&& matrix[x1-1][y1] ==0 && !visited[x1-1][y1] ){
                q.offer(new int[]{x1-1,y1});
                visited[x1-1][y1] = true;
            }

            //하
            if(x1+1<matrix.length && matrix[x1+1][y1]==0 && !visited[x1+1][y1]){
                q.offer(new int[]{x1+1,y1});
                visited[x1+1][y1] = true;

            }

            //좌
            if(y1>0 && matrix[x1][y1-1]==0 && !visited[x1][y1-1]){
                q.offer(new int[]{x1,y1-1});
                visited[x1][y1-1] = true;
            }

            //우
            if(y1+1<matrix[0].length && matrix[x1][y1+1]==0 && !visited[x1][y1+1]){
                q.offer(new int[]{x1,y1+1});
                visited[x1][y1+1] = true;
            }
            /// //////////////////// 탐색 끝 ////////////////////////////

        }

        //녹인 부분을 카운트 하면서 0으로 교체
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(matrix[i][j]==2){
                    count++;
                    matrix[i][j]=0;
                }
            }
        }

        //치즈가 다 사라졌다면
        if(count==0){
            over=true;
        }
        else {
            lastCheeseCount=count;
        }

        //탐색이 끝나면 시간을 증가시키고 다시 새롭게 탐색하기 위해 초기화
        totalTime++;
        visited=new boolean[N][M];
    }


    public static void main(String[] args) throws IOException {

        //N M 입력
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N= Integer.parseInt(st.nextToken());
        M= Integer.parseInt(st.nextToken());

        //동적 할당
        matrix=new int[N][M];
        visited=new boolean[N][M];

        //행열 값 입력
        for (int i = 0; i < N; i++) {
            st=new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                matrix[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        //치즈가 모두 없어질때 까지 반복
        while(!over){
            //bfs 탐색 시작
            bfs(0,0);
        }

        //최종 결과 출력
        System.out.println(totalTime);
        System.out.println(lastCheeseCount);

    }

}

 

마무리하며:

처음에는 치즈를 중심으로 탐색하면서 외곽 치즈를 찾아 제거하는 방식으로 구현하려 했다.
하지만 내부 공기와 외부 공기를 구분하는 것이 생각보다 까다로웠고, 외곽 치즈만 정확히 걸러내는 것도 쉽지 않았다.

 

결국 시선을 바꿔, 치즈가 아닌 공기를 기준으로 탐색하는 방식으로 전환했다.
외부 공기부터 BFS를 수행하며 인접한 치즈를 처리하는 방식이 더 명확하고 안정적인 해법이었다.

 

이번 문제를 풀면서 처음 생각한 방향이 막히면, 관점을 바꿔보는 게 중요하다는 걸 다시 한번 느꼈다.
다음에 유사한 문제를 마주하더라도, 중심 대상을 바꾸거나 흐름을 반대로 추적하는 등 다른 방식으로 접근해보려는 시도가 필요할 것이라고 느꼈다.

 

감사합니다.