[BOJ]3197번: 백조의 호수

www.acmicpc.net/problem/3197

---

R, C 값이 크기 때문에 직접 하루하루씩 날짜를 올리면서 BFS를 돌리면 O(N^3)으로 시간초과가 납니다.

(R,C를 N으로 퉁치겠습니다.)

 

1. 맨 처음에 BFS 탐색을 통해 가장 마지막에 녹는 빙판의 날짜 MAXV 를 구합니다.

2. 1번 값에 의해서 백조가 만나게 되는 날의 후보는 0~MAXV 사이에 존재합니다.

3. 0~MAXV 날짜 사이의 후보값을 이분탐색으로 BFS를 돕니다.

4. 그러면 시간복잡도는 O(N^2LogN)이 되서 제한시간 내에 통과할 수 있습니다.

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ3197.cc