[BOJ]1800번: 인터넷 설치

 

www.acmicpc.net/problem/1800

---

justicehui님의 풀이를 보고 해결했습니다. (justicehui.github.io/usaco/2019/07/12/BOJ1800/)

 

단순히 DFS를 돌려버리면 터지므로 다익스트라 + 결정 문제로 바꿔서 해결합니다.

 

"특정 가중치 이하의 간선으로만 경로를 구성할 수 있는가?"를 결정하는 문제로

 

특정 가중치가 넘는 간선에 대해서는 1의 가중치를 주고

특정 가중치가 넘지 않는 간선에 대해서는 0에 가중치를 주어

다익스트라를 돌립니다.

 

만든 최단 경로가 K 이하의 가중치로 도달가능하다면 이 값은 가능한 값으로

저장해놓고 mid를 더 줄여서, 더 작은 가중치로 다시 연결 시켜봅니다.

 

만든 최단 경로가 K 이하의 가중치로 도달이 불가능하다면 mid를 올려서

더 높은 가중치를 기준으로 다시 연결을 시켜봅니다.

 

전부 돌려본 후 저장해놓은 최소값을 리턴하면 됩니다.

justicehui님의 풀이를 보기 전까진 결정문제인지도 눈치 못챘던 문제입니다ㅠㅠ

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1800.cc