1800 인터넷 설치( 다익스트라 ,이분탐색)

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

1800번: 인터넷 설치

1.접근

간단한 문제인거같아 DFS로 목적지에 도달했을때 stack을 정렬해서 값을 찾아냈는데 시간초과를 받았다.(정렬을 너무 많이 사용하게 되서)

'x원으로 해결이 안되는데 x-1원으로 가능할까?' 라는 질문글에 있던 힌트를 보고 문제를 해결할 수 있었다.

 

2.풀이

이분탐색을 해가면서 다익스트라를 돌릴때마다 가능한 값이면 정답에 저장하도록 했다.

문제에서 남은선중 가장 비싼 하나의 값만 가지기로 했으므로 이분탐색으로 확인하는 값 이하인 길이는 가중치0, 확인하는 값 이상의 길이는 가중치1로 두고 다익스트라를 변형하여 풀어야한다.

1~N으로의 최단경로가 k 보다 커지면 불가능하고 도착할 수 있다면 정답으로 바꿔준다.

 

+헷갈렸던 부분)

이분탐색 가능 여부에 대해서 헷갈렸었다.

기준 잡은 값이 존재하지 않을 수 있는 거 아닌가? 라는 의문을 가졌지만 그건 최대값 구하는 문제일때 생기는 상황이였었다. 최소값을 구하는 것이므로 존재하는 값을 기준으로 나눠졌다.

 

3.코드

4.배운점

• 다익스트라를 문제 상황에 맞게 변형해서 풀어나가는 것에 익숙해지자.
• 다익스트라의 시간복잡도 O(E * log E)를 다시 복습했다.(모든 간선을 확인 E + 모든 간선을 우선순위 큐에 넣음ElogE)