이분탐색. [1939]

[1. 문제 설명]

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

---

[2. 풀이 접근]

시도 혹은 시도해보려 했던 오답인 풀이

1. 유니온-파인드
   => 공장이 있는 섬과 같은 집합에 속한 섬들이 존재
   => 공장1에서 공장2로 갈때 이 섬들을 거쳐서만 갈 수 있다.
   => 즉, 이 집합에 속한 섬들을 연결 하는 edge 중 최소 weight 를 찾는다.
   ==> 틀린 이유
   # 특정 경로를 선택 하였을 때, 위에서 선택 된 최소 weight 를 갖는 edge 를 거치지 않을 수 있다.
2. BFS 에서 모든 경로 탐색
   => BFS 에서 visit 을 업데이트 하지 않으면 모든 경로 탐색이 가능 할까라는 생각에서 출발
   => 그래프 유형은 약간 다르지만, visit 을 업데이트 하지 않고 풀이가 가능했던 문제가 있었다.
   ## https://testkernelv2.tistory.com/445
   => 하지만 모든 노드가 서로 연결된 그래프인 경우
   => 그 경로가 너무 많아서 시간초과 발생할 가능성이 매우 높음.

===== 정답이었던 풀이 =====

정수 C 의 범위가 매우 길다.

=> 풀이 시, 이분 탐색을 고려해볼 수 있다.

=> 그래프 탐색에 BFS 를 이용한다.

=> BFS 와 이분 탐색이 조합 된 형태의 문제이다,

=> 어떻게 보면, 최적화 문제를 결정 문제로 바꿔서 푸는 형태라고 볼 수 있다.

 

먼저 bfs 에서 edge weight 의 하한 값을 설정하여

이 하한 값 보다 작은 weight 를 갖는 edge 는 탐색  시 사용하지 않도록 한다.

 

이 하한 값을 C 가 표현하는 구간에 대해서 이분 탐색을 진행하여 하한 값을 결정하고,

이 하한 값을 기저로하여 bfs 탐색을 수행한다.

• weight 의 하한 값으로 경로 탐색이 성공한 경우
  => 최대 중량을 선정하기 위해
  => (mid, max] 인 탐색의 상위 구간에서 이분 탐색을 진행
• 경로 탐색이 실패한 경우
  => [min, mid) 인 탐색의 하위 구간에서 이분 탐색을 진행

bfs 의 결과는 전체 경로에서 사용 된 edge 중 weight 의 최소 값을 반환하도록 한다.

• 전체 경로의 중량 제한을 결정하는 요소이기 때문이다.

이분 탐색은 bfs 가 성공 할 경우

현재 까지 bfs 의 결과와 비교하여 최대 weight 를 갱신하도록 한다.

---

[3. 코드]