[백준 / 1880] 인터넷 설치 (Python)

 

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

1800번: 인터넷 설치

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:52:57

 

---

 

문제 설명

 

오늘 팀전을 다들 열심히 하시는 것을 보고 원장선생님은 세미나 실에 인터넷을 설치해 주기로 마음을 먹으셨다. 하지만 비 협조적인 코레스코 콘도는 원장님께서 학생들에게 인터넷 선을 연결하는 것에 대해서 일부에 대해 돈을 요구하였다.

각각의 학생들의 번호가 1부터 N까지 붙여져 있다고 하면 아무나 서로 인터넷 선이 연결되어 있지 않다. P(P<=10,000)개의 쌍만이 서로 이어 질수 있으며 서로 선을 연결하는데 가격이 다르다.

1번은 다행히 인터넷 서버와 바로 연결되어 있어 인터넷이 가능하다. 우리의 목표는 N번 컴퓨터가 인터넷에 연결하는 것이다. 나머지 컴퓨터는 연결 되어 있거나 연결 안되어 있어도 무방하다.

하지만 코레스코에서는 K개의 인터넷 선에 대해서는 공짜로 연결해주기로 하였다. 그리고 나머지 인터넷 선에 대해서는 남은 것 중 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 이때 원장선생님이 내게 되는 최소의 값을 구하여라.

 

입력 및 출력

 

입력

첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차례로 들어온다. 가격은 1 이상 1,000,000 이하다.

 

출력

첫째 줄에 원장선생님이 내게 되는 최소의 돈을 출력한다. 만약 1번과 N번 컴퓨터를 잇는 것이 불가능 하다면 -1을 출력한다.

 

입력 예시

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

 

출력 예시

4

 

 

---

 

풀이

 

간만에 재밌는 문제를 푼 것 같다..!

 

1에서 N으로 향하는 여러 경로를 전부 탐색하는 건 당연히 시간초과. 즉 다른 접근법이 필요하다.

 

이분 탐색을 진행하되, 이분 탐색의 조건을 '기준의 cost 초과는 무조건 스킵하면서 N까지 도달할 수 있는지 여부'로 결정해 보자. 즉 1부터 N까지 향하는 경로를 찾으면서, 경로상의 cost가 기준 cost보다 높으면 무조건 skip하게 된다(K번째까지 무료이므로)

 

• 만약 N까지 도달 가능한 경우가 존재하면, end = mid - 1으로 설정함으로써 더 낮은 기준 cost가 있는지 탐색한다.
• 그렇지 않다면 start = mid + 1로 설정함으로써 가능한 더 높은 기준 cost가 있는지 탐색한다.

 

탐색은 다익스트라 알고리즘을 이용하여 진행하되, 앞서 말한 기준 cost가 초과하는 경로일 경우 skip하는 알고리즘을 추가하도록 한다.

 

• init : 초기화함수, N, P, K와 P개의 경로를 입력받아, 경로 딕셔너리를 생성한다.
• dijkstra : 다익스트라 알고리즘을 통해 N으로 가는 경로를 검사한다.
  • cost는 max_cost를 기준으로 검사한다.
  • skip 개수가 K가 넘어가는 경우는 제외해야 한다.
  • 모든 경로 탐색이 끝난 후, cost_list[N]의 최솟값을 반환한다.
• binary_search : 이분탐색함수. 가격의 최솟값인 1부터 최대값인 1000000까지 이분 탐색을 실행한다. 각 mid값에 대해 dijkstra를 호출하고, 반환받은 값을 토대로 다음 탐색 범위를 정한다. 만약 가능한 경우 minimal value를 업데이트한다. 모든 탐색이 종료되면 업데이트된 minimal value를 반환한다.
• solve : 메인함수. init 함수로 모든 변수 및 리스트를 초기화하고, binary_search로 반환받은 minimal value를 출력한다. 만약 전혀 업데이트가 되지 않았다면 모든 경우에 불가능하다는 의미이므로 -1을 출력한다.

 

 

 

 

풀이 코드

from heapq import *
from collections import defaultdict, deque
import sys
input = sys.stdin.readline

MAX = float('inf')

def init() :
  global N, P, K, web_dict
  N, P, K = map(int, input().split())
  web_dict = defaultdict(list)
  for i in range(P) :
    a, b, cost = map(int, input().split())
    web_dict[a].append((b, cost))
    web_dict[b].append((a, cost))


def dijkstra(huddle) :
  q = [(0, 1, K)]
  cost_list = [[MAX]*(K+1) for _ in range(N+1)]
  cost_list[1][K] = 0

  while q :
    cost, node, skip_left = heappop(q)
    if node == N :
      continue

    for next_node, _cost in web_dict[node] :
      if _cost > huddle :
        next_skip_left = skip_left - 1
        next_cost = cost
      else :
        next_skip_left = skip_left
        next_cost = max(cost, _cost)

      if next_skip_left < 0 :
        continue

      if cost_list[next_node][next_skip_left] > next_cost :
        cost_list[next_node][next_skip_left] = next_cost
        heappush(q, (next_cost, next_node, next_skip_left))

  result = min(cost_list[N])
  return result

def binary_search() :
  start, end = 1, 1000000
  result = MAX
  while start <= end :
    mid = (start + end) // 2

    _result = dijkstra(mid)
    if _result < MAX :
      end = mid - 1
      result = min(result, _result)
    else :
      start = mid + 1

  return result

def solve() :
  init()
  result = binary_search()
  print(result if result < MAX else -1)

solve()

 

풀이 완료~