BOJ) 치즈

치즈

2636번: 치즈

처음에는, 4면을 검사하면서 공기와 접촉하지 않은 치즈들의 지워지는 시간을 1시간씩 증가 시켰었다.

하지만, 문제의 조건에서 모든 공기가 치즈를 녹이는 것이 아니라, 가장 외부에 있는 공기들만 치즈를 녹인다는 조건이 있었다.

또한, 맵의 테두리는 공기로만 주어진다는 조건이 있어서 BFS를 이용했다.

 

외부 공기의 위치와 가장 외부에 노출된 치즈의 위치를 저장할 큐 두 개를 선언해주었다.

0,0을 시작으로 외부 공기를 큐에 저장하면서, 가장 외부에 닿은 치즈들의 좌표 또한 다른 큐에 저장했다.

모든 외부 공기를 순환하고 난 뒤, 외부에 노출된 치즈의 좌표를 빼내면서 녹여준 후, 카운트를 하나씩 줄여주었다. 또한, 녹은 치즈는 공기가 되니까 가장 외부 공기 queue에 넣어주었다.

 

모든 치즈가 녹을 때 까지 이 과정을 반복하면서, 한 시간마다 (로직이 한번 실행될 때 마다) 남은 치즈 개수를 따로 담은 LinkedList에 저장했다.)

이 LinkedList의 size의 시간만큼 지나야 모든 치즈가 녹음을 의미하고, 가장 마지막에 담겨있는 요소가 치즈가 모두 녹기 한 시간 전에 남은 치즈 수를 의미한다.

 

풀이

 

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

public class Cheese_2636 {
  static final char CHEESE ='1', AIR ='0';
  static final int[] dx = {0,0,-1,1}, dy = {1,-1,0,0};

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    char[][] map = new char[n][m];
    int total =0;

    for(int i=0; i<n; i++) {
      st = new StringTokenizer(br.readLine());
      for(int j=0; j<m; j++) {
        map[i][j] = st.nextToken().charAt(0);
        if(map[i][j] == CHEESE) {
          total++;
        }
      }
    }

    br.close();
    solution(n,m,map, total);
  }

  private static void solution(int n, int m, char[][] map, int total) {
    LinkedList<Integer> remainCheeses = getRemainsQueue(n,m,map,total);
    StringBuilder sb = new StringBuilder();
    sb.append(remainCheeses.size()).append("\n");
    sb.append(remainCheeses.pollLast());
    System.out.println(sb.toString());
  }

  private static LinkedList<Integer> getRemainsQueue(int n, int m, char[][] map, int total) {
    Queue<Pos> airQueue = new LinkedList<>(), outerCheeseQueue = new LinkedList<>();
    LinkedList<Integer> remainCheeses = new LinkedList<>();
    airQueue.offer(new Pos(0,0));
    boolean[][] visit = new boolean[n][m];
    visit[0][0] = true;


    while(total >0) {
      remainCheeses.offer(total);
      while (!airQueue.isEmpty()) {
        Pos air = airQueue.poll();

        for (int i = 0; i < 4; i++) {
          int nx = air.x + dx[i], ny = air.y + dy[i];
          if (isInArea(nx, ny, m, n) && !visit[ny][nx]) {
            Pos now = new Pos(nx, ny);
            visit[ny][nx] = true;
            if (map[ny][nx] == AIR) {
              airQueue.offer(now);
            } else {
              outerCheeseQueue.offer(now);
            }
          }
        }
      }
      while (!outerCheeseQueue.isEmpty()) {
        Pos outerCheese = outerCheeseQueue.poll();
        total--;
        airQueue.offer(outerCheese);
        map[outerCheese.y][outerCheese.x] = AIR;
      }
    }
    return remainCheeses;
  }

  private static boolean isInArea(int x, int y, int m, int n) {
    return x >=0 && x<m && y>=0 && y<n;
  }

  private static class Pos {
    int x,y;

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