도로포장 ( 1162 번 )

1162번: 도로포장

---

🧠 알고리즘

• 다익스트라(Dijkstra) + 다중 상태 DP 기반 최단 경로 탐색

 

✔️ 동작 방식

• 문제 핵심 아이디어
  서울(1번 도시)에서 포천(n번 도시)까지 이동하는 최단 시간을 계산하되, 최대 k개의 도로를 포장하면 시간 0 처리 가능.
  즉, 각 도시마다 “지금까지 포장한 도로 수별 최소 이동 시간”을 관리하며, 다익스트라로 최단 경로를 갱신하는 문제.

 

• 주요 로직 요약

1. 그래프 구성 (_mk_conn)
   • 각 도로(a, b, c)를 양방향으로 연결 리스트에 저장 (연결 도시, 통과 시간).
2. DP 테이블 초기화 (_main)
   • dp[현재 도시][포장한 도로 수] = 걸린 시간
   • 모든 값은 무한대로 초기화, 시작점 서울은 dp[1][0] = dp[1][1] = 0.
3. 우선순위 큐를 사용한 탐색
   • (현재시간, 현재노드, 포장한 도로 수)를 기준으로 최소 시간 순으로 탐색.
   • 가지치기: 현재 시간이 DP 값보다 크면 더 이상 탐색하지 않음.
4. 다음 노드로 이동
   • 포장하지 않고 이동: sum_time = now_time + next_time
   • 포장하고 이동: sum_time = now_time (시간 0) + 포장 횟수 증가
   • DP 갱신 시 새로운 상태를 큐에 추가.
5. 최종 결과
   • 도착 도시(n)에서 가능한 모든 포장 수 상태의 최소 시간 중 최솟값 반환.

---

 

🧾 코드

import sys, heapq

def _mk_conn(n, m):
    answer = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        answer[a].append((b, c))
        answer[b].append((a, c))

    return answer

def _main(n, k, conn):
    """
        dp[현재 도시][현재 포장한 도로수]
        값 : 걸린 시간
    """
    dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]

    # 서울( 1 ) 부터 레츠고고 
    dp[1][0] = dp[1][1] = 0
    hq = [(0, 1, 0)] # (현재시간, 현재노드, 현재 포장한 갯수)

    while hq:
        now_time, now_node, road_count = heapq.heappop(hq)
        
        if now_time > dp[now_node][road_count]: # 탐색 필요없는 경우면
            continue

        for next_node, next_time in conn[now_node]:
            sum_time = now_time + next_time
            # 포장 안함
            if sum_time < dp[next_node][road_count]:
                dp[next_node][road_count] = sum_time
                heapq.heappush(hq, (sum_time, next_node, road_count))

            # 포장 ㄱㄱ
            if (road_count < k) and (now_time < dp[next_node][road_count + 1]):
                dp[next_node][road_count + 1] = now_time
                heapq.heappush(hq, (now_time, next_node, road_count + 1))

    return min(dp[n])
    

n, m, k = map(int, sys.stdin.readline().rstrip().split())
conn = _mk_conn(n, m)
print(_main(n, k, conn))

---

 

⏱️ 시간 복잡도

while hq : 각 노드를 방문 ( 선형 시간 )
	now_time, now_node, road_count = heapq.heappop(hq) : 힙 연산 ( 로그 시간 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )