기로에 서다

문제 www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 풀이 1. 빙하가 녹는 시간마다 BFS를 돌릴 때, 최악의 경우 $O(R*C*max(R,C))$로 TLE가 난다. 2. 이에 빙하가 녹는시간을 BFS 한번으로 전처리한 후, 빙하가 녹는 시간에 대한 백조의 이동을 줄여보기로 한다. 3. 백조가 만날 수 있는 최소시간이 T초일 때, T-1초엔 녹지않은 빙하때문에 만날 수 없다는 점에서 "시간이 T일 때 백조가 만날 수 있는 가?" 라는 결정함수..