백준 1939: 중량제한 (Swift)

어떻게 풀어야할까 그 알고리즘을 생각하는데 꽤 오래걸린 문제이다.

다익스트라? Floyd-Warshall? 모두 가능해보였다.

결국 플로이드 워셜 알고리즘으로 풀이를 했지만,  메모리가 128MB이기 떄문에 메모리 초과가 뜨고 말았다.

 

풀이를 검색해보니, 다익스트라 혹은 이분탐색 + BFS 형태 , 즉 Parametric Search형태의 문제였다.

 

아래는  이분탐색 + BFS 방식으로 풀이한 코드이다.

이분탐색 방식으로 우리가 옮길 짐의 무게를 차례로 탐색한다. => 그떄그떄의 무게를 bfs함수에 전달하여, 해당 무게의 짐을 옮길때 다리를 건너 도착지까지 갈 수 있는지를 Bool 형태로 return해준다.