문제

이해

NxM 크기의 모눈종이 위에 치즈가 놓여져 있다. 주어진 격자에는 3가지 유형의 칸이 존재한다.

3가지 유형으로는 치즈, 치즈 바깥, 치즈 안이 있다.

치즈는 시간이 지날 때마다 사라지는데 사라지는 조건은 다음과 같다.

치즈는 격자의 4면중 2면 이상이 바깥 공기와 접촉하면 사라진다.

시간이 지날 때마다 외부의 공기로 인해 치즈는 사라지고 치즈가 완전히 사라지기 까지의 시간을 출력하자.

접근

공기에 해당하는 0은 위처럼 치즈 바깥, 치즈 안이 존재할 수 있다.

처음 풀이에는 치즈 안을 조사하려 했다.

    while (!q.isEmpty()) {
      xy now = q.poll();

      for (int i = 0; i < 4; i++) {
        int new_x = now.x + d_row[i];
        int new_y = now.y + d_col[i];

        if (new_x < 2 || new_x >= N - 2 || new_y < 2 || new_y >= M - 2) {
          return;
        }

        if (cheese[new_x][new_y] == 1) {
          continue;
        }
        if (visited[new_x][new_y]) {
          continue;
        }

        q.add(new xy(new_x, new_y));
        InnerSpaces.add(new xy(new_x, new_y));
        visited[new_x][new_y] = true;
      }
    }

위는 치즈 내부를 체크하는 코드의 일부분이다. 치즈 내부가 외부로 연결되어 있는 경우 return하고 아니라면 지나온 공간들을 모두 2로 처리해 내부 공간으로 정의하였다.

하지만 당연하게도(?) 내부 공간을 조사할 필요가 없다..

왜냐하면 외부 공간을 조사하는게 훨씬 쉽기 때문이다.

    while (!q.isEmpty()) {
      xy now = q.poll();

      for (int i = 0; i < 4; i++) {
        int new_x = now.x + d_row[i];
        int new_y = now.y + d_col[i];

        if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M) {
          continue;
        }

        if (visited[new_x][new_y]) {
          continue;
        }

        if (cheese[new_x][new_y] == 1) {
          continue;
        }
        q.add(new xy(new_x, new_y));
        cheese[new_x][new_y] = 2;
        visited[new_x][new_y] = true;
      }
    }

위처럼 굳이 List를 사용하지 않고 외부 공간을 2로 표현하면 쉽게 구분 가능하다.

그렇다면 이제 치즈를 녹일 차례이다.

치즈는 존재하는 공간마다 4방향으로 탐색하고 외부 공간이 2면 이상이라면 삭제하면 된다.

이는 치즈의 개수가 0이 될 때까지 반복한다.

코드

package java_baekjoon;

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

public class prob2638_2 {
  static int N;
  static int M;
  static int[][] cheese;
  static int sec;
  static int[] d_row = { -1, 0, 1, 0 };
  static int[] d_col = { 0, 1, 0, -1 };
  static boolean[][] visited;
  static ArrayList<xy> arr_cheese;
  static int cheese_cnt = 0;

  static class xy {
    int x;
    int y;

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

  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());
    cheese = new int[N][M];
    arr_cheese = new ArrayList<>();

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());

      for (int j = 0; j < M; j++) {
        cheese[i][j] = Integer.parseInt(st.nextToken());
        if (cheese[i][j] == 1) {
          arr_cheese.add(new xy(i, j));
          cheese_cnt++;
        }
      }
    }

    while (cheese_cnt != 0) {
      sec++;
      visited = new boolean[N][M];
      SetOuterAir(new xy(0, 0));
      CheeseMelting();
    }

    System.out.println(sec);
  }

  static void CheeseMelting() {
    for (int i = 0; i < arr_cheese.size(); i++) {
      xy now = arr_cheese.get(i);
      int cnt = 0;

      for (int j = 0; j < 4; j++) {
        int new_x = now.x + d_row[j];
        int new_y = now.y + d_col[j];

        if (cheese[new_x][new_y] == 2) {
          cnt++;
        }
      }

      if (cnt >= 2) {
        cheese[now.x][now.y] = 0;
        cheese_cnt--;
        arr_cheese.remove(i--);
      }
    }
  }

  static void SetOuterAir(xy cdnt) {
    Queue<xy> q = new LinkedList<>();
    q.add(cdnt);
    cheese[cdnt.x][cdnt.y] = 2;
    visited[cdnt.x][cdnt.y] = true;

    while (!q.isEmpty()) {
      xy now = q.poll();

      for (int i = 0; i < 4; i++) {
        int new_x = now.x + d_row[i];
        int new_y = now.y + d_col[i];

        if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M) {
          continue;
        }

        if (visited[new_x][new_y]) {
          continue;
        }

        if (cheese[new_x][new_y] == 1) {
          continue;
        }
        q.add(new xy(new_x, new_y));
        cheese[new_x][new_y] = 2;
        visited[new_x][new_y] = true;
      }
    }
  }
}

결과

처음에는 치즈를 녹일 때 BFS를 사용했다. BFS를 통해 방문하는 칸마다 조사하게 했는데 메모리 초과가 발생했다.