3197. 백조의 호수

이 문제의 대회 데이터가 공개되어 있으니 사용해 보자. 원문 제목은 labudovi이다.

3197번: 백조의 호수

---

얼음을 녹이면서 백조가 만날 수 있는지 확인해야 한다.

 

물과 인접한 얼음이 녹는다는 설명에서 BFS를 적용해야 함을 알 수 있다. 그런데 $O(V^3)$짜리 단순한 BFS로는 시간 초과를 받는다. 

 

사실 이 글은 3197번에 대한 풀이라기보단 최적화를 이루기 위한 나의 장대한 일대기라고 불러도 좋을 것이다. 집에만 있으니까 조금 이상해졌나 보다.

 

BFS를 시작할 칸을 찾을 때

BFS를 할 때마다 $O(V^2)$짜리 탐색을 하는 것은 좋지 않다. 대신 queue의 원소를 계속 재사용하면 시간을 줄일 수 있다. 즉 어떤 BFS의 단말 노드(더 이상 탐색할 칸이 없는 원소)는 다음 BFS의 시작 원소이므로, 이것들을 저장해 놓으면 다음 BFS를 즉시 시작할 수 있다.

 

Case 1. 백조가 움직이다가..

- 물을 만났을 때: 탐색 queue에 넣고 계속 움직인다.

- 얼음을 만났을 때: 지금 탐색할 수는 없지만, 다음 날에 얼음이 녹으면 이 칸을 탐색할 수 있다. 따로 저장했다가 이번 탐색이 끝난 후 탐색 queue로 모두 옮겨야 한다.

- 다른 백조를 만나면: 정답을 구했다!

 

Case 2. 얼음이 녹는데..

- 주변 칸이 얼음이라면: 다음 날에 이 칸이 녹을 예정이므로, 오늘 녹을 얼음과 별도로 저장했다가 재활용하자. 위의 2번에서 얼음을 만났을 때와 같은 맥락이다.

- 주변 칸이 물이라면: 무시한다.

 

무언가 퍼져나가는 BFS를 구현할 때, 위의 방법론을 사용하여 시간을 줄일 수 있다. 이 문제의 강화판으로 14868. 문명이 있으니 한번 도전해 보자. 난 안 할거다.

---