[Java] 백준 BOJ / 2638번: 치즈

치즈

문제

---

문제 설명

N X M 크기의 모눈종이 위에 치즈의 위치정보가 1로 주어진다.

치즈는 공기에 두 면 이상이 노출 되면 1시간 후에 사라지는데 치즈로 둘러쌓인 공기는 노출되었다고 치지 않는다.

격자의 정보가 주어졌을 때 치즈들이 모두 녹는데 얼마나 걸리는지 계산하는 문제이다.

---

구현

일단 기본적인 그래프 탐색이기 때문에 BFS 를 사용하는 것은 확실했다.

이 문제에서 구현하기 어려운 거는 치즈로 둘러쌓인 공기들을 어떻게 판단할 것인가 였다.

문제 조건에서 보면 "맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다." 라는 말이 있다.
생각을 해보면 왼쪽 위부터 시작하는 공기들이 이어지는 곳들은 외부의 공기이고 그렇지 않으면 다 치즈로 둘러쌓인 공기가 된다.

그래서 BFS를 치즈가 다 사라질 때까지 돌리는데 그래프를 탐색을 하면서 외부 공기만을 체크를 해준다면 나머지 공기들은 내부이기 때문에 신경을 안써도 된다.

일단 치즈가 다 없어질 때까지 돌려야하기 때문에 입력을 받을 때 cheeseCount 를 세서 while문에 넣어준다.

그리고 tempArr 를 만들어서 기존의 arr를 복사해주고 좌표 (0, 0) 에서 BFS 함수를 시작한다.

while (cheeseCount > 0) {
	// tempArr에 arr 복사
	tempArr = new int[n][m];
	for (int i = 0; i < n; i++) {
		tempArr[i] = arr[i].clone();
	}

	// 0,0 은 항상 외부이므로 해당 칸에서 시작하는 곳들은 tempArr에서 다 3으로 초기화
	bfs(0,0);
    
    //구현
}  

BFS 함수에서는 시작 좌표인 (0, 0) 에서부터 시작해서 외부 공기들을 체크를 해주면 된다.

방문했다는 표시겸 해서 외부 공기라고 3 으로 초기화해주었다.

  public static void bfs(int x, int y) {
    queue = new LinkedList<>();
    queue.add(new int[]{x, y});
    while (!queue.isEmpty()) {
      int[] cur = queue.poll();
      for (int i = 0; i < 4; i++) {
        int nx = cur[0] + dx[i];
        int ny = cur[1] + dy[i];

        if (nx >= 0 && ny >= 0 && nx < n && ny < m && tempArr[nx][ny] == 0) {
          //방문했다는 표시로 3으로 초기화
          tempArr[nx][ny] = 3;
          queue.add(new int[]{nx, ny});
        }
      }
    }
  }

이렇게 BFS 가 한번 끝나면 외부 공기들은 모두 3으로 초기화가 된 tempArr 가 생긴다.

이 상태에서 없어질 치즈들을 확인을 해주어야 한다. 기존의 배열인 arr를 확인해주면서 치즈인 경우, 해당 치즈에서의 상하좌우를 보면서 맞닿은 공기 면적들을 확인한다. 이때 공기는 tempArr 를 기준으로 확인한다.
그리고 맞닿은 공기 면적인 airCount 변수가 2 이상이면 arr 에서 치즈를 0으로 바꿔주고 cheeseCount 를 1 감소시키면 된다.

이렇게 한 플로우가 끝나면 time을 1 증가 시키고 다시 위의 tempArr 만들기 -> BFS로 외부 공기 체크하기 -> 녹는 치즈 확인 과정을 cheesCount 가 0이 될때까지 반복하면 된다.

---

코드

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

public class Main_2638 {
  static int n, m;
  static int cheeseCount;
  static int[][] arr;
  static boolean[][] visited;
  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, -1, 0, 1};
  static int[][] tempArr;
  static Queue<int[]> queue;
  //걸리는 시간
  static int time;

  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());

    arr = new int[n][m];

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

    //치즈가 다 녹아 없어질 때까지 반복
    while (cheeseCount > 0) {
      // tempArr에 arr 복사
      tempArr = new int[n][m];
      for (int i = 0; i < n; i++) {
        tempArr[i] = arr[i].clone();
      }

      // 0,0 은 항상 외부이므로 해당 칸에서 시작하는 곳들은 tempArr에서 다 3으로 초기화
      bfs(0,0);

      //없어질 치즈 확인 후 삭제
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          //치즈인 경우
          if (arr[i][j] == 1) {
            int airCount = 0;
            for (int dir = 0; dir < 4; dir++) {
              int nx = i + dx[dir];
              int ny = j + dy[dir];
              if (nx >= 0 && ny >= 0 && nx < n && ny < m && tempArr[nx][ny] == 3) {
                airCount++;
              }
            }
            if (airCount >= 2) {
              arr[i][j] = 0;
              cheeseCount--;
            }
          }
        }
      }
      time++;
    }
    System.out.println(time);
  }

  public static void bfs(int x, int y) {
    queue = new LinkedList<>();
    queue.add(new int[]{x, y});
    while (!queue.isEmpty()) {
      int[] cur = queue.poll();
      for (int i = 0; i < 4; i++) {
        int nx = cur[0] + dx[i];
        int ny = cur[1] + dy[i];

        if (nx >= 0 && ny >= 0 && nx < n && ny < m && tempArr[nx][ny] == 0) {
          //방문했다는 표시로 3으로 초기화
          tempArr[nx][ny] = 3;
          queue.add(new int[]{nx, ny});
        }
      }
    }
  }
}