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

문제

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

---

[사용한 알고리즘]

• 다익스트라
• 이분 탐색

[알고리즘]

본 문제를 처음 시도하였을때, 조합을 이용해 모든 인터넷 설치의 경우의 수를 구한 뒤, 각 경우의 수에 대한 연산을 해주었다. 결과는 몰론 당연하게도 메모리 초과로 실패하였다.

생각해보면 P의 범위가 $1<=P<=10000$ 이므로 모든 조합의 경우의 수를 구하면, $_{10000}{C}_{1}$ + $_{10000}{C}_{2}$ + $…$ + $_{10000}{C}_{10000}$ $= 2^{10000}$ 이라는 어마어마한 숫자가 나온다. 아마 평생 계산해도 못끝냈을 양이다.d

즉 문제에서 P의범위를 제대로 보았다면 이러한 멍청한 연산은 하지 않았을 것이다. 고로 항상 문제를 잘 읽자..

여하튼 이 문제는 검색을 해본 결과 이분탐색 + 다익스트라 를 이용한 풀이가 존재했다. 이것 또한 생각해보면, 각 노드간 가중치가 주어져 있기에 최소거리를 찾는다는 개념으로 다익스트라를 생각하고 접근하고 생각했어야 했는데 많이 부족했다.

알고리즘 설명

1. 이분 탐색을 수행한다. ( 즉 돈을 낼 최소 비용을 이분 탐색을 통하여 결정합니다. )
2. left , right 값을 통하여 mid값을 구합니다.
3. 다익스트라를 수행합니다. 이때, 핵심은 최소 거리를 구하는 것이 아닌 지불할 수 있는 최소비용인 mid 값보다 큰 비용의 개수를 구하는 것 입니다.
4. 따라서 distance[] 에는 mid 값을 넘긴 케이블의 수가 들어 있습니다.
   • 즉 distance[n] > k 라면 n 까지 가는데 공짜 케이블 k개로는 해결할 수 없다는 의미입니다.
5. 위의 과정을 계속 반복합니다. ( 즉 가장 적정의 값을 찾을 때 까지 반복한다는 의미 입니다. )

import sys
import heapq
input = sys.stdin.readline

N, P, K = map(int,input().split())
INF = 1e15
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, right = 0, 1000001
answer = INF

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 item in graph[index]:
            if item[1] > limit:
                if cost + 1 < distance[item[0]]:
                    distance[item[0]] = cost + 1
                    heapq.heappush(q, (cost + 1, item[0]))
            else :
                if cost < distance[item[0]]:
                    distance[item[0]] = cost
                    heapq.heappush(q, (cost , item[0]))
                    
    if distance[N] > K:
        return False
    else:
        return True

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)

---

참고 블로그 : https://jjangsungwon.tistory.com/125