[Python] 백준 3197. 백조의 호수

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

Python3으로는 통과한 사람이 없는 문제. PyPy를 써야 통과 가능하다.

 

매 초마다 빙하가 녹는 지점을 찾고, 백조끼리 연결이 가능한지 확인하다 보면

R, C <= 1500이라는 조건 때문에 시간초과가 나는 문제.

 

도저히 모르겠어서 풀이 로직을 검색해서 찾아보니

BFS + 이분탐색으로 '최소 시간'을 찾아내는 방식으로 풀어야 했다.

 

1. 바다 / 백조를 기준으로, 빙하의 각 위치는 '몇 초 후면' 녹아 없어지는지를 배열에 저장한다. (time 배열)

2. '시간'을 기준으로 이분탐색을 진행한다. n초가 지난 후 백조끼리 연결이 가능한지를 time 배열로 확인한다.

3. 이분탐색으로 최솟값을 구해 리턴한다.