인터넷 설치 (1800번) - 백준 (BOJ)

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

1800번: 인터넷 설치

 

 

백준 - 인터넷 설치 (1800번)

 

난이도 : Gold 1

알고리즘&자료구조 : Priority Queue (우선순위 큐) / Dijkstra (다익스트라) / 정렬 (Sorting)

시간복잡도 (Time Complexity) : O( (N)log(P) * log(max(L)) )

 

▷ 아이디어 떠올리기가 상당히 어려운 문제였다.

---

★ 핵심 Idea ★

 

◎ 다익스트라 함수를 일반적인 최단거리 찾기가 아닌,

1번 컴퓨터와 N번 컴퓨터를 연결하는 데 필요한 케이블들 중

"특정 가격"보다 높은 가격의 케이블 수를 찾는 함수로 변형하는 것이 필요하다.

 

그리고 파라메트릭 서치를 통해 위의 "특정 가격"을 바꿔가면서,

가능한 가장 작은 가격을 찾는 것이 문제의 풀이 방법이다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline
from heapq import heappop, heappush


class Farm():
    def __init__(self, N, P, K):
    	### 간선 입력받아서 그래프 생성
        graph = [[] for _ in range(N+1)]
        prices = []
        for _ in range(P):
            n1, n2 , price = map(int, input().split())
            prices.append(price)
            graph[n1].append((price, n2))
            graph[n2].append((price, n1))
        ### 중복되는 가격 제외하고 오름차순 정렬
        ### 앞에 0을 붙이는 이유 : 돈을 내지 않아도 되는 경우 찾기 위함
        prices = [0] + sorted(set(prices))
        
        self.N = N
        self.graph = graph
		
        ### 만약 다익스트라 결과 N 노드의 거리가 갱신되지 않으면
        ### N 노드는 연결되어있지 않으므로 답은 -1이 됨 
        if self._dijkstra(1) == N:
            self.minimum = -1
        ### N 노드가 1 노드와 연결된 경우 : Parametric Search 실행
        else:
            s, e = 0, len(prices)-1
            while s < e:
                m = (s+e)>>1
                ### pay : 1번 노드와 N번 노드를 연결하는 데 필요한 케이블들 중
                ### prices[m]보다 높은 가격의 케이블 갯수
                pay = self._dijkstra(prices[m])
                if pay <= K:
                    e = m
                else:
                    s = m+1
            self.minimum = prices[e]

	
    ### 다익스트라 함수 :
    ### 현재 비용 thres을 기준으로 1번 노드부터 N번 노드까지 연결할 때,
    ### thres보다 높은 가격의 케이블이 몇 개 필요한지 확인
    def _dijkstra(self, thres):
    	### dist[x] : 1번 노드부터 x번 노드를 연결하는 데 필요한 케이블 중,
        ### thres보다 높은 가격의 케이블 개수
        dist = [self.N] * (self.N+1)
        ### 1번 노드부터 시작
        dist[1] = 0
        pq = [(0, 1)]
        while pq:
            p, n = heappop(pq)
            if dist[n] < p:
                continue
            for pp, nn in self.graph[n]:
            	### 만약 현재 케이블의 가격이 thres보다 작거나 같다면
                ### 1번 노드부터 nn 노드까지 연결된 케이블 중
                ### thres보다 높은 가격의 케이블의 갯수는 여전히 p
                
            	### 만약 현재 케이블의 가격이 thres보다 높다면
                ### 1번 노드부터 nn 노드까지 연결된 케이블 중
                ### thres보다 높은 가격의 케이블의 갯수는 현재 케이블을 포함한 p+1
                
                pp = p if pp <= thres else p+1
                if dist[nn] <= pp:
                    continue
                dist[nn] = pp
                heappush(pq, (pp, nn))
                
        ### 1번 노드와 N번 노드를 연결하는 데 필요한 케이블들 중, thres보다 높은 가격의 케이블 갯수 출력
        return dist[self.N]


if __name__ == '__main__':
    farm = Farm(*map(int, input().split()))
    print(farm.minimum)