2636번: 치즈

문제

사각형 모양의 판 위에 치즈가 놓여 있습니다. 이 치즈는 공기와 접촉하면 한 시간 뒤에 녹아 없어집니다. 단, 치즈 내부에 있는 빈 공간(구멍)은 외부 공기와 닿지 않는 것으로 취급되어, 구멍과만 닿아있는 치즈는 녹지 않습니다. 모든 치즈가 녹아 없어지는 데 걸리는 시간과, 치즈가 모두 녹기 한 시간 전에 남아있던 치즈 조각의 개수를 구하는 문제입니다.

• 입력: 첫째 줄에 판의 세로와 가로 길이가 주어지고, 둘째 줄부터 판의 모양(1은 치즈, 0은 빈 칸)이 주어집니다.
• 출력: 첫째 줄에 치즈가 모두 녹아서 없어지는 데 걸리는 시간, 둘째 줄에 모두 녹기 한 시간 전에 남아있는 치즈 조각의 개수를 출력합니다.

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

풀이: 외부 공기 기준 BFS 탐색

이 문제의 핵심은 '외부 공기'와 '내부 공기(치즈 안의 구멍)'를 구분하는 것입니다. 이를 위해 무조건 외부 공기임이 보장되는 모서리(가장자리), 즉 (0, 0) 좌표에서 탐색을 시작하는 것이 포인트입니다.

1. 외부 공기 탐색 시작: 매 시간마다 (0, 0)에서 BFS 탐색을 시작합니다. 방문 배열(visited)을 새로 초기화하고, 외부 공기만을 따라 이동합니다.
2. 치즈 발견 및 저장 (내부 침투 방지): 상하좌우를 탐색하다가 빈 공간(0)을 만나면 큐에 넣어 계속 탐색합니다. 만약 치즈(1)를 만나면, 이는 외부 공기와 맞닿은 치즈이므로 이번 시간에 녹아야 할 대상입니다. 치즈를 만난 경우에는 더 이상 안쪽으로 탐색을 진행하지 않기 위해 큐에 넣지 않고 별도의 list에 좌표만 저장해 둡니다.
3. 치즈 녹이기: BFS 탐색이 한 번 끝나면 list에 담겨 있는(공기와 맞닿은) 치즈들의 좌표를 모두 찾아 배열에서 0으로 바꾸어 녹입니다.
4. 시간 및 개수 기록: 루프를 반복하며 치즈가 녹을 때마다 시간(time)을 1씩 증가시키고, 방금 녹인 치즈의 개수(list.size())를 cnt에 저장해 둡니다. 만약 BFS 결과 list가 비어있다면, 더 이상 녹일 치즈가 없는(모두 녹아버린) 상태이므로 시뮬레이션을 종료합니다. 반복문 종료 후 남아있는 cnt가 모두 녹기 한 시간 전의 치즈 개수가 됩니다.

코드

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

public class Main {
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

       int time = 0;
       int cnt = -1; // 마지막 남은 치즈 개수를 저장할 변수
       
       while (true) {
          List<Node> list = new ArrayList<>();
          Queue<Node> q = new LinkedList<>();
          boolean[][] visited = new boolean[n][m];
          
          // 외부 공기와 맞닿은 부분을 찾기 위해 항상 (0, 0)에서 시작
          q.add(new Node(0, 0));
          visited[0][0] = true;

          // BFS 수행
          while (!q.isEmpty()) {
             Node node = q.poll();
             for (int i = 0; i < 4; i++) {
                int ny = node.y + dy[i];
                int nx = node.x + dx[i];
                
                // 맵을 벗어나거나 이미 방문한 곳은 무시
                if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                   continue;
                if (visited[ny][nx])
                   continue;
                   
                visited[ny][nx] = true;
                
                // 치즈를 만난 경우: 큐에 넣지 않고 리스트에만 추가하여 외부 공기만 스캔
                if (a[ny][nx] == 1) {
                   list.add(new Node(ny, nx));
                } 
                // 빈 공간인 경우: 계속 탐색을 위해 큐에 추가
                else {
                   q.add(new Node(ny, nx));
                }
             }
          }

          // 더 이상 녹을 치즈가 없다면 종료
          if (list.isEmpty())
             break;

          // 시간 증가 및 직전에 녹인 치즈 조각 수 기록
          time++;
          cnt = list.size();

          // 모아둔 바깥쪽 치즈들을 일괄적으로 녹임 (0으로 변경)
          for (Node node : list) {
             a[node.y][node.x] = 0;
          }
       }

       bw.write(time + "\n" + cnt);

       bw.flush();
    }

    static class Node {
       int y, x;

       Node(int y, int x) {
          this.y = y;
          this.x = x;
       }
    }
}

알고리즘 분류

그래프 탐색, 너비 우선 탐색 (BFS), 시뮬레이션