백준 알고리즘: 2636번 치즈

문제 정보

---

 

2636번: 치즈

 

 

핵심

---

BFS(너비 우선 탐색)을 사용하여 문제를 풀이한다!

이를 사용하는 근거는, 치즈 조각은 한 시간이 지날때 마다 점차 녹아가며 우리가 구해야 하는 것은 모든 경로를 탐색하는 것이 아닌 각자의 위치(공기)에서 녹일 수 있는 치즈를 천천히 녹여가며 모든 치즈가 녹는 데에 걸린 시간과 한 시간 전에 남아있는 치즈 조각을 구하는 것이기 때문이다

사실상 이를 떠올리는 것은 어렵지는 않고, 좀 까다로웠던 것은

(0,0) 부터 맵을 탐색하기 시작하여 0(공기)이면 큐에 추가하고, 1(치즈)이면 이를 0(공기)로 바꿔주고 전체 치즈 카운트를 하나씩 줄여 주는것.

그리고 한 사이클이 돌면(한 시간이 지나면)에 따라 남은 치즈의 개수, 녹인 치즈 개수, 한 시간이 지났음을 기록해야 하므로

visited 배열은 bfs()가 실행될 때마다 초기화해주고(1시간 마다), 다시 (0,0)부터 실행하면 된다.

 

 

풀이

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  static int[][] map;
  static boolean[][] visited;
  static int numberOfRow;
  static int numberOfCol;
  static int[] moveToRow = {0, 0, 1, -1};
  static int[] moveToCol = {1, -1, 0, 0};

  public static void main(String[] args) throws Exception {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    numberOfRow = Integer.parseInt(st.nextToken());
    numberOfCol = Integer.parseInt(st.nextToken());
    map = new int[numberOfRow][numberOfCol];

    int numberOfCheese = 0;
    for (int r = 0; r < numberOfRow; r++) {
      st = new StringTokenizer(br.readLine());
      for (int c = 0; c < numberOfCol; c++) {
        int number = Integer.parseInt(st.nextToken());
        map[r][c] = number;
        if (number == 1) {
          numberOfCheese++;
        }
      }
    }
    // input end

    int time = 0;
    int currentMelt = 0;
    while (numberOfCheese > 0) {
      currentMelt = bfs();
      time += 1;
      numberOfCheese -= currentMelt;
    }

    System.out.println(time);
    System.out.println(currentMelt);
  }

  public static int bfs() {
    visited = new boolean[numberOfRow][numberOfCol];
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0});
    int meltingCheese = 0;
    while (!queue.isEmpty()) {
      int[] current = queue.poll();
      for (int i = 0; i < 4; i++) {
        int currentRow = current[0] + moveToRow[i];
        int currentCol = current[1] + moveToCol[i];

        if (currentRow < 0 || currentRow >= numberOfRow || currentCol < 0
            || currentCol >= numberOfCol || visited[currentRow][currentCol]) {
          continue;
        }

        if (map[currentRow][currentCol] == 0) {
          queue.add(new int[]{currentRow, currentCol});
        } else {
          map[currentRow][currentCol] = 0;
          meltingCheese++;
        }
        visited[currentRow][currentCol] = true;
      }
    }
    return meltingCheese;
  }
}

 

Source Code on GitHub

---