[백준 1800] 인터넷 설치 - Python

문제 보기

 

[사용한 알고리즘]

다익스트라, 이분 탐색

 

[알고리즘]

알고리즘 전체 과정을 대략적으로 말씀드리면 이분 탐색을 통해 케이블 기준 가격을 정한 후 다익스트라를 수행함으로써 1번과 N번 컴퓨터를 이을 수 있는지 판단합니다. 세부적인 과정은 다음과 같습니다.

 

1. 이분 탐색을 수행하기 위해 left, right 값을 0과 1000001로 초기화합니다.

2. left와 right를 통해 mid 값을 구한 후 다익스트라를 수행합니다.

3. 다익스트라 수행은 기존의 다익스트라와 달리 최소 거리를 구하는 것이 아니라 1번과 N번을 연결할 수 있는지 구하는 것이 핵심입니다. 따라서 거리 값은 mid 값을 넘긴 케이블의 수입니다.

 - 만약 distance[n] 값이 k보다 크면 공짜로 제공하는 케이블선 k개로는 1번과 N번을 연결할 수 없다는 의미입니다. 

4. 위 과정을 left 값이 right 값보다 클 때까지 반복합니다.

5. 최종적으로 구한 결과를 출력합니다.

 

[코드]

import heapq
import sys


INF = 1e15


def dijkstra(start, limit):
    q = []
    distance = [INF] * (n + 1)
    heapq.heappush(q, (0, start))  # (가중치, 인덱스)
    distance[start] = 0

    while q:
        cost, index = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[index] < cost:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인하면서 거리 업데이트
        for i in graph[index]:
            if i[0] > limit:
                if cost + 1 < distance[i[1]]:
                    distance[i[1]] = cost + 1
                    heapq.heappush(q, (cost + 1, i[1]))
            else:
                if cost < distance[i[1]]:
                    distance[i[1]] = cost
                    heapq.heappush(q, (cost, i[1]))

    # limit 보다 큰 가격 k개 이상이면 False
    if distance[n] > k:
        return False
    else:
        return True


if __name__ == "__main__":
    n, p, k = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(p):
        a, b, c = map(int, sys.stdin.readline().split())
        graph[a].append((c, b))
        graph[b].append((c, a))

    left, right = 0, 1000001
    answer = INF
    while left <= right:
        mid = (left + right) // 2
        flag = dijkstra(1, mid)
        if flag:
            right = mid - 1
            answer = mid
        else:
            left = mid + 1

    if answer == INF:
        print(-1)
    else:
        print(answer)