[ baekjoon ] 1162. 도로포장

ayoung0073·2021년 3월 11일
0

baekjoon

목록 보기
51/59
post-thumbnail

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

소스코드

## 1162. 도로 포장

import sys
import heapq

input = sys.stdin.readline
INF = int(1e10)

n, m, k = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [[INF for _ in range(k + 1)] for _ in range(n + 1)]

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

def dijkstra():
  q = []
  # hour, node, count
  distance[1][0] = 0
  heapq.heappush(q, (distance[1][0], 1, 0))
  while q:
    hour, now, cnt = heapq.heappop(q)
    if distance[now][cnt] < hour: # 이미 갱신된 상태면 continue
      continue
    for i, j in graph[now]:
    # i : node, j : hour
      if cnt + 1 <= k and hour < distance[i][cnt + 1]: 
      # 포장할 때. 순서 바뀌면 index error
        distance[i][cnt + 1] = hour
        heapq.heappush(q, (distance[i][cnt + 1], i, cnt + 1))
      if hour + j < distance[i][cnt]:
      # 포장하지 않는 경우
        distance[i][cnt] = hour + j
        heapq.heappush(q, (hour + j, i, cnt))

dijkstra()
print(min(distance[n]))

2차원 배열 distance를 선언하고, 먼저 INF를 대입한다.
distance[v][cnt] : 1번 도시에서 v번 도시까지 cnt개의 도로를 포장해서 가는 최단 거리

다익스트라를 이용해 각 도시까지의 최단 거리를 찾을 수 있다.
두가지 경우로 나뉘어서 heappush를 진행하면 된다.

1. 포장할 수 있는 경우

if cnt + 1 <= k and hour < distance[i][cnt + 1]: 

이 조건에서 주의할 것은 두개의 조건 순서가 바뀌면 안된다.
cnt + 1 <= k 을 만족해야 두번째 조건에서 index error가 발생하지 않기 때문이다.

2. 포장하지 않을 경우

포장하지 않고, 해당 distance보다 짧을 경우, 갱신한 뒤 heappush를 진행한다.

나의 실수

움,, INF 값 실수,, 때문에 10번 넘게 제출했드앗..
10억(1e9)이 아니라 100억(1e10)을 대입하니 바로 성공 ㅠ

profile
백엔드 공부 -ing

0개의 댓글