안녕하세요. BFS를 단 2번만 하는데 시간초과가 발생합니다. 

이해가 조금 어려운 부분인데 혹시 제가 놓치고 있는 부분이 있다면 도와주시면 감사하겠습니다. 

전체 방향은 다음과 같습니다.

1. 먼저 오늘 깰 수 있는 얼음을 한방에 깬다. (BFS 1회)

2. 얼음을 깬 후, 오늘 백조가 탐색할 수 있는 곳을 한번에 다 탐색한다. (BFS 1회)

While문 안에서 1,2를 반복하는데 무슨 BFS가 2번이냐? 라고 하실 수 있는데 제가 생각하기에는 두 번입니다.

1. 얼음을 깨는 부분

다음 얼음이 깨질 부분은 오늘 얼음이 깨질 부분입니다. 오늘 얼음이 깨지는 부분이 새롭게 물이 생기는 부분이고, 물이 생기는 부분의 동서남북으로만 얼음이 있는지 체크하면 빠지지 않고 얼음을 깰 수 있습니다. 즉, 각 칸을 한번씩만 체크해주면 되는데  동서남북으로 중복 방문하는 경우를 감안하더라도 4번씩 방문가능합니다. 이것을 시간복잡도로 환산하면 (4N^2) = N^2이므로, 얼음을 깨는데 필요한 모든 경우의 수는 N^입니다. 즉, 2,250,000입니다.

2. 백조가 날아가는 부분

백조도 얼음과 비슷하게 동작합니다. 백조는 오늘 날아갈 수 있는 최대한으로 날아가고 마지막 위치를 기록합니다. 다음 날, 얼음이 깨지면 현재 백조가 탐험한 마지막 위치부터 추가 탐색을 하는 것이 가장 효율적입니다. 왜냐하면 백조가 마지막으로 탐색한 위치는 얼음과의 경계면이기 때문에 가장자리입니다. 또한 백조가 마지막으로 탐색한 위치는 물입니다. 따라서 이 위치를 기반으로 동서남북으로 탐색할 여지가 생기게 됩니다. 따라서 이전에 탐색했던 위치를 더 탐색하지 않습니다.  즉 N^2만큼 탐색합니다.

위의 경우의 수를 합치면 시간 복잡도는 N^2 정도로 TLE가 발생하지 않아야 합니다. 그런데 실제로는 TLE가 발생합니다.

1500 * 1500에 (0,0) / (1499,1499)를 제외한 곳에 백조를 놔두고 완료되는데 시간을 측정해보면 실제로는 10초 가량의 시간이 걸리는 것이 확인됩니다. 각각의 시간 분배는 1번 함수는 총 3초 정도, 2번 함수는 총 7초 정도의 시간을 잡아 먹고 있습니다. 

실제 생각하는 것과 측정되는 시간이 꽤 다르게 나오는데.. 혹시 제가 이상하게 생각하고 있는 부분이 있거나, 놓치고 있는 부분이 있다면 알려주시면 감사하겠습니다.