BOJ 2636:: 치즈 – DFS & 다익스트라

acmicpc.net/problem/2636

DFS

먼저 외부 공기와 치즈 내부 구멍을 구분할 필요가 있으니 외부를 0이 아니라 2로 다 바꿔버립시다. 재귀함수 써서 DFS 구현해주면 됩니다. (BFS도 상관 없지만 크기가 그리 크지 않아 스택 오버플로 일어날 일이 없으니 그냥 DFS 썼습니다.)

그리고 반복문을 돌립니다. 먼저 외부 공기(2)와 접촉해있는 치즈(1)를 다 찾은 다음 (2중 for문) 그런 치즈는 녹는다고 했으니까 2로 바꿉니다. 그리고 녹은 치즈와 인접한 칸이 0이면 그 치즈가 녹으면서 외부 공기와 내부 구멍이 만나게 되는 것이므로 아까와 똑같이 DFS를 써서 해당 0과 인접한 0들을 다 2로 놓습니다.

만약 치즈가 한 칸도 없다면 반복문을 종료하고, 그 때까지 반복한 횟수가 녹는데 걸리는 시간이 됩니다. 다 녹기 한 시간 전 치즈 개수는 반복문 돌 때마다 각 시각별로 녹는 치즈 개수를 저장해주면 알 수 있죠.

fill은 DFS로 2를 채우는 함수, canMelt는 그 치즈가 외부 공기와 접촉해있는지 판정하는 함수입니다. 각 시각별로 녹는 치즈 개수를 NumMelt에 저장합니다.

다익스트라

각 칸을 그래프의 꼭짓점으로 두고 인접한 칸 사이에 변을 놓아줍시다. (보통 알고리즘 문제에서 자주 나오는 형태입니다.) 각 변마다 가중치를 어떻게 주나면…

  • 치즈가 없는 칸  치즈가 없는 칸 : 0
  • 치즈가 없는 칸  치즈가 있는 칸 : 1
  • 치즈가 있는 칸  치즈가 없는 칸 : 0
  • 치즈가 있는 칸  치즈가 있는 칸 : 1

그리고 제일 왼쪽 위 (0, 0)를 시작점으로 두고 다익스트라로 모든 칸에 대해 최단거리를 구합니다. 이 최단거리가 첫 번째 풀이에서 구했던 해당 칸이  0 또는 1에서 2가 되는데 걸리는 시간입니다. 그럼 다 녹는데 걸리는 시간은 초기에 치즈가 있던 칸들의 최단거리 중 최댓값이고 다 녹기 한 시간 전 치즈 개수는 그 최댓값을 최단거리로 하는 원래 치즈가 있던 칸의 개수입니다.