2638번 : 치즈 [JAVA]

문제링크

성공 여부(걸린 시간): 성공(28분 40초)

아이디어

이 문제의 핵심은 “외부 공기”와 닿은 치즈만 녹는다는 조건을 정확하게 구현하는 것이다. 단순히 값이 0인 칸을 전부 공기로 취급해버리면, 치즈 안에 갇힌 공기(내부 구멍)까지 외부 공기로 잘못 인식해서 오답이 나온다.
그래서 코드 전체 구조는 다음 두 단계가 한 턴(time step)에 반복되는 형태다.

1. 현재 시점 기준으로 “외부 공기”가 어디까지 퍼져 있는지 BFS로 탐색
2. 그 외부 공기와 두 면 이상 접촉하는 치즈를 한 번에 녹이기

이를 코드 흐름에 맞춰 정리해보면 다음과 같다.

---

1. 입력 및 기본 세팅

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int [][] map = new int[N][M];
...
if(x=='1'){
    map[i][j] = 1;
}

• N x M 판을 map 배열로 저장하고, 치즈가 있는 칸만 1로 표시한다.
• 치즈가 아닌 곳은 기본값 0(공기)로 유지된다.
• 이후 시뮬레이션을 위해 방향 배열 dx, dy와 시간(턴 수)인 turn을 준비한다.

int [] dx = {1, 0, -1, 0};
int [] dy = {0, 1, 0, -1};
int turn=0;

flag는 “이번 턴에 치즈가 하나라도 있었는지”를 기록하기 위한 불리언이다. 치즈가 하나도 없으면 시뮬레이션을 끝내기 위해 사용한다.

---

2. 한 턴마다 외부 공기(BFS)부터 다시 계산

while (flag){
    flag = false;
    boolean [][] outAir = new boolean[N][M];
    // 외부 공기 BFS
    ArrayDeque<int []>q = new ArrayDeque<>();
    q.add(new int[]{0,0});
    outAir[0][0] = true;
    while (!q.isEmpty()){
        int [] cur = q.poll();
        for(int i=0; i<4; i++){
            int mx = cur[0]+dx[i];
            int my = cur[1]+dy[i];
            if(canGo(mx, my)&&map[mx][my]!=1&&!outAir[mx][my]){
                q.add(new int[]{mx, my});
                outAir[mx][my] = true;
            }
        }
    }
    ...
}

• 모든 턴의 시작에서 outAir 배열을 새로 만든다.
  → 이유: 치즈가 녹으면 공기의 구조가 매 턴 달라지므로, 매번 “지금 기준의 외부 공기”를 다시 계산해야 한다.
• (0, 0)에서 BFS를 시작하는 이유:
  • 문제 조건상 판의 가장자리는 공기로 둘러싸여 있고, (0,0)은 항상 외부 공기라고 볼 수 있다.
  • 여기서 시작해서 치즈(값 1)를 만나기 전까지의 모든 0 칸들은 “외부와 연결된 공기”다.
• BFS 조건 map[mx][my] != 1:
  • 치즈 칸은 통과할 수 없으므로, 치즈를 기준으로 바깥과 안쪽 공기가 차단된다.
  • 이 덕분에 치즈 안쪽에 갇힌 “내부 공기”는 BFS로 도달할 수 없고, outAir가 true로 찍히지 않는다.
    → 즉, 내부 구멍은 외부 공기로 취급되지 않는다.

결과적으로 이 BFS가 끝나면 outAir[x][y] == true인 칸은 “이번 턴 기준 외부 공기”이고, false인 0칸들은 내부 구멍이다.

---

3. 외부 공기와 두 면 이상 접촉한 치즈 찾기

//녹아내릴 치즈 ArrayList에 추가
ArrayList<int[]> removeCheese = new ArrayList<>();
for(int i=1; i<N-1; i++){
    for(int j=1; j<M-1; j++){
        if(map[i][j]==1){
            //치즈가 만약 없었다면 끝내줘야함
            flag = true;
            int outAirCnt = 0;
            for(int dir = 0; dir<4; dir++){
                int mx =i+dx[dir];
                int my =j+dy[dir];
                if(outAir[mx][my]){
                    outAirCnt++;
                }
            }
            if(outAirCnt>=2){
                removeCheese.add(new int[]{i,j});
            }
        }
    }
}

• 내부만 보면, 이중 for문으로 전체 배열을 돌면서 map[i][j] == 1인 치즈 칸만 검사한다.
• 치즈 칸을 발견했다는 것 자체가 “아직 치즈가 남아있다”는 의미이므로 flag = true로 갱신한다.
• 그 치즈 칸의 상하좌우를 보면서, outAir가 true인 외부 공기 칸이 몇 개 붙어 있는지 센다.
  • outAirCnt >= 2이면 “이번 턴에 녹을 치즈”이므로 removeCheese 리스트에 좌표를 저장한다.
• 이때 한 칸이 동시에 녹거나 안 녹거나 해야 하므로, 바로 map을 수정하지 않고 일단 리스트에 좌표만 모아두었다가 나중에 한 번에 처리한다.

이 과정을 통해 “이번 시간에 녹을 치즈”만 정확히 골라내게 된다.

---

4. 종료 조건과 치즈 제거

//남아있는 치즈가 없는 경우
if(!flag){
    System.out.print(turn);
    return;
}
//치즈제거
for(int [] x: removeCheese){
    map[x[0]][x[1]] = 0;
}
turn++;

• 만약 전체 순회를 도는 동안 치즈를 한 번도 만나지 않았다면(flag == false), 더 이상 녹일 치즈가 없다는 의미다.
  • 이때까지 누적된 turn이 곧 전체 치즈가 녹는 데 걸린 시간이다.
  • 바로 turn을 출력하고 끝낸다.
• 반대로 치즈가 있었다면(flag == true), removeCheese에 모아둔 좌표들을 실제로 0으로 바꾸면서 “이번 턴의 녹기”를 반영한다.
  • 그리고 turn++ 해서 다음 턴으로 넘어간다.

이 과정을 while(flag) 안에서 반복하기 때문에, 치즈가 완전히 사라질 때까지 시뮬레이션이 진행된다.

---

5. 보조 함수: 범위 체크

static boolean canGo(int x, int y ){
    return x>=0 && y>=0 && x<N && y<M;
}

BFS와 인접 탐색을 할 때 공통으로 사용하는 범위 체크 함수다.
인덱스가 배열의 범위를 벗어나지 않는지만 단순하게 검사한다.

---

6. 전체 풀이 정리

정리하면, 이 코드는 매 시간마다 다음을 반복하는 시뮬레이션 + BFS 구조다.

1. (0,0)에서 시작하는 BFS로 “외부 공기” 위치(outAir)를 매번 새로 계산한다.
2. 모든 치즈 칸을 돌면서, 외부 공기와 접촉한 변의 개수를 센다.
   • 두 면 이상 닿은 치즈를 리스트에 모아둔다.
3. 이번 턴에 녹을 치즈를 한 번에 0으로 만들고, 시간(turn)을 1 증가시킨다.
4. 더 이상 치즈가 없으면(flag == false) 누적된 turn을 출력하고 종료한다.

이렇게 하면 내부 구멍은 끝까지 외부 공기로 취급되지 않기 때문에, 문제에서 요구하는 “외부 공기와 두 면 이상 접촉한 치즈만 턴마다 녹는다”는 규칙을 정확하게 구현할 수 있다. 전체 시간 복잡도는 매 턴마다 O(N*M) (BFS + 전체 순회)이고, 치즈가 최대 N*M 턴 동안 녹을 수 있다고 해도 충분히 통과 가능한 수준이다.

풀이 코드

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

public class Main {
    static int N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int [][] map = new int[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                char x = st.nextToken().charAt(0);
                if(x=='1'){
                    map[i][j] = 1;
                }
            }
        }
        boolean flag = true;
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        int turn=0;
        while (flag){
            flag = false;
            boolean [][] outAir = new boolean[N][M];
            // 외부 공기 BFS
            ArrayDeque<int []>q = new ArrayDeque<>();
            q.add(new int[]{0,0});
            outAir[0][0] = true;
            while (!q.isEmpty()){
                int [] cur = q.poll();
                for(int i=0; i<4; i++){
                    int mx = cur[0]+dx[i];
                    int my = cur[1]+dy[i];
                    if(canGo(mx, my)&&map[mx][my]!=1&&!outAir[mx][my]){
                        q.add(new int[]{mx, my});
                        outAir[mx][my] = true;
                    }
                }
            }
            //녹아내릴 치즈 ArrayList에 추가
            ArrayList<int[]> removeCheese = new ArrayList<>();
            for(int i=1; i<N-1; i++){
                for(int j=1; j<M-1; j++){
                    if(map[i][j]==1){
                        //치즈가 만약 없었다면 끝내줘야함
                        flag = true;
                        int outAirCnt = 0;
                        for(int dir = 0; dir<4; dir++){
                            int mx =i+dx[dir];
                            int my =j+dy[dir];
                            if(outAir[mx][my]){
                                outAirCnt++;
                            }
                        }
                        if(outAirCnt>=2){
                            removeCheese.add(new int[]{i,j});
                        }
                    }
                }
            }
            //남아있는 치즈가 없는 경우
            if(!flag){
                System.out.print(turn);
                return;
            }
            //치즈제거
            for(int [] x: removeCheese){
                map[x[0]][x[1]] = 0;
            }
            turn++;
        }
    }
    static boolean canGo(int x, int y ){
        return x>=0 && y>=0 && x<N && y<M;
    }
}