문제 출처 : https://www.acmicpc.net/problem/3197
"처음엔 정답률 19%가 쉽게 풀려서 기분이 좋았지만, 시간초과 때문에 멘탈이 갈려버린 문제.."
문제 정리
- 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
- 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
- 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
- 백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
- 며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
문제 해결 방법
문제를 처음 보고 다음과 같은 방법으로 시도를 했다.
- BFS로 얼음을 녹이고 map을 업데이트 시킨다.
- 해당 map에서 두 백조가 만날 수 있는지 BFS 탐색을 시도한다.
- 만날 수 없다면 day++를 하고 1, 2번을 반복한다.
- 만나는 경우에 day를 출력한다.
아마 대부분 이 방법을 생각할 것이다. 하지만 시간초과가 나와버린다.