1800. 인터넷 설치 (Python)

1800번: 인터넷 설치

 

풀이

 이분탐색과 다익스트라를 결합하여 해결하는 문제다. 과정은 다음과 같다.

 

1. 먼저 이분탐색을 통해 기준이 되는 가격을 설정한다.

2. 그 후 다익스트라를 통해서 1번과 N번을 연결한다.

3. 이 때, 기존에는 dist 배열에 시작 지점부터 해당 지점까지의 최단 거리를 넣어줬는데 이번 문제에서는 기준 가격을 넘는 케이블을 몇 개 사용했는지를 담는다.

4. 마지막에 dist[N]의 값이 공짜로 제공되는 케이블선의 개수인 K개 이하인지를 체크한다.

 

 만약, dist[N]의 값이 K개 이하라면 기준 가격으로 1번과 N번을 연결할 수 있음을 뜻한다.

 

코드

import sys
import heapq
input = sys.stdin.readline
INF = float('INF')

# base: base를 초과하는 가격을 가진 케이블을 공짜로 사용한다.
def dijkstra(base):
    q = []
    heapq.heappush(q, (0, 1))
    dist = [INF for _ in range(N+1)] # dist[n]: 1번부터 n번을 연결하는 데 사용된 공짜 케이블 개수 
    dist[1] = 0

    while q:
        d, now = heapq.heappop(q)

        if dist[now] < d:
            continue

        for (next, nextDist) in graph[now]:
            cost = d
            if nextDist > base: # 기준 가격을 초과한다면 
                cost += 1 # 공짜 케이블 개수를 하나 증가시킨다.

            if cost < dist[next]:
                dist[next] = cost
                heapq.heappush(q, (cost, next))

    # 1번과 N번을 연결하는 데 K개 이하의 공짜 케이블이 사용된다면
    # base 가격은 정답이 될 수 있다.
    return dist[N] <= K 


if __name__ == '__main__':
    # N: 학생들의 번호, P: 케이블선의 개수, K: 공짜로 제공하는 케이블선의 개수
    N, P, K = map(int, input().split())
    graph = [[] for _ in range(N+1)] # 케이블 선 정보

    for _ in range(P):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))

    left = 0
    right = 1_000_000
    res = -1

    while left <= right:
        mid = (left + right) // 2 # 이분 탐색으로 기준 가격 설정

        if dijkstra(mid):
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    print(res)