백준 / 최소비용 구하기 2 / 11779번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 최소비용 구하기 2 / 11779번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/11779

 

문제 설명

---

나의 풀이

정답 코드

import heapq


def dijkstra(graph, n, m, start, end):
    # 결과 값
    answer = []

    # 힙: (비용, 현재 위치)
    heap = [(0, start)]

    # 거리 배열: 무한대로 초기화
    INF = int(1e9)
    dist = [INF] * (n + 1)
    dist[start] = 0

    # 경로 추적을 위한 부모 테이블
    parent = [0] * (n + 1)

    while heap:
        distance, current = heapq.heappop(heap)

        # 이미 더 짧은 경로로 처리된 노드면 스킵
        if dist[current] < distance:
            continue

        for next_city, next_distance in graph[current]:
            cost = distance + next_distance
            if cost < dist[next_city]:
                dist[next_city] = cost
                parent[next_city] = current
                heapq.heappush(heap, (cost, next_city))

    # 경로 복원
    channel = []
    now = end
    while now != 0:
        channel.append(now)
        now = parent[now]
    channel.reverse()

    # 결과값 저장
    answer.append(dist[end])
    answer.append(len(channel))
    answer.append(channel)

    # 결과 출력
    print(answer[0])
    print(answer[1])
    for city in answer[2]:
        print(city, end=' ')
    print()


def main():
    n = int(input())  # 도시 개수
    m = int(input())  # 버스 개수

    # 그래프 형성
    graph = {i: [] for i in range(1, n + 1)}

    for _ in range(m):
        a, b, dis = map(int, input().split())
        graph[a].append((b, dis))  # 단방향 그래프

    # 시작과 끝
    start, end = map(int, input().split())

    dijkstra(graph, n, m, start, end)


if __name__ == "__main__":
    main()

이전의 잘못된 부분

# 힙: (비용, 현재 위치)
    heap = [(0, start)]

    # 방문 처리
    visited = [False] * (n + 1)

    # 총 비용
    total_distance = 0

    # 경로 추적을 위한 부모 테이블
    parent = [0] * (n + 1)

    # 힙에 push할 때 직전 도시 임시 저장용
    temp_parent = [0] * (n + 1)

    while heap:
        distance, current = heapq.heappop(heap)

        if visited[current]:
            continue
        visited[current] = True

        # parent 확정 (start는 제외)
        if current != start:
            parent[current] = temp_parent[current]

        if current == end:
            total_distance = distance
            break

        for next_city, next_distance in graph[current]:
            if not visited[next_city]:
                heapq.heappush(heap, (distance + next_distance, next_city))
                temp_parent[next_city] = current

다익스트라를 처리하는 과정에서 방문 처리를 하는 경우 나중에 더 짧은 경로를 찾을 수 있음에도 불구하고 다시 못찾게 되는 경우가 발생할 수 있습니다. 그래서 방문 처리가 아닌 제일 짧은 경우보다 길 경우 예외처리 하는게 옳습니다.

---

※ 알아야 할 것

다익스트라를 이용한 최단거리를 구하는 문제는 방문처리를 하는 경우에는 오답이 발생할 수 있습니다. 왜냐하면 다익스트라의 본래 원칙이 최단 거리가 확정된 노드만 방문처리를 해야하기 때문입니다.