[파이썬/Python] 백준 1504(🥇4): 특정한 최단 경로

숨·2025년 8월 15일

코테

알고리즘 문제 풀이

목록 보기

113/128

📌 문제 : 백준 1504

📌 문제 탐색하기

N : 정점의 개수 ( $2 ≤ N ≤ 800$ )
E : 간선의 개수 ( $0 ≤ E ≤ 200000$ )

문제 풀이

1번 정점에서 N번 정점까지 가는데 반드시 특정 2개의 정점을 거쳐서 가는 최단 경로를 구하는 문제이다.

최단 경로는 최소의 가중치를 가질 경우 이동한 경로이므로 가중치있는 최단 거리를 고려할 때 사용하는 다익스트라(힙 활용)를 구현한다.

방향성이 없는 그래프이므로 입력되는 두 정점 모두에 연결 정보를 입력해주어야 한다.

또한 v1, v2 중 어디를 먼저 거쳐야 하는지에 대한 조건이 없으므로 2가지 조건을 고려해주어야 한다.

1 → v1 → v2 → N
1 → v2 → v1 → N

다익스트라 함수가 시작점, 도착점을 입력으로 받도록 하여 각 경로 별로 최단 경로 거리를 구하고 합한 후, 두 경우 중 더 짧은 경로를 출력으로 내보내도록 구현한다.

이동 경로가 없다면 -1을 출력해야 하므로 최단 거리 저장 리스트의 값이 초기와 변화가 없다면 -1을 출력하도록 구현한다.

가능한 시간복잡도

힙 연산을 3번 반복 → $O(3((N+E)logN)) = O((N+E)logN)$

최종 시간복잡도
최악일 때 $O((N+E)logN) = O(200800 * log(800))$ 이 되는데 이는 제한시간 1초 내 충분히 수행 가능하다.

알고리즘 선택

각 정점까지의 최단 경로 구하는 함수를 다익스트라 구현해 거리 계산

📌 코드 설계하기

다익스트라 구현
입력받기
2가지 경로에 대해 다익스트라 실행
조건에 따라 출력

📌 시도 회차 수정 사항

1회차

처음엔 다익스트라를 한번 수행해서 전체 이동한 정점들을 저장하고 그 저장한 리스트에 반드시 지나야 하는 두 정점이 있는지 확인하는 방식으로 하려고 했다. 그렇게 되니 연산량은 많아지는데 조건으로 제어하기 어려웠다.
1번 정점 → v1 정점 → v2 정점 → N번 정점으로 이동하는 사이사이에 다익스트라를 호출하는 것이, 1번에서 N번으로 가는 모든 최단 경로를 찾는 것보다 나을 것이란 판단이 들었다.

2회차

입력을 넣고 엔터를 눌렀음에도 결과가 나오지 않았다. 강제 종료했을 때 위의 위치에서 진행되지 않았음을 확인했다.
계산한 누적 거리를 거리 저장 리스트에 저장해주어야 하는데 그 코드가 빠져서 계산이 진행되지 않아 발생한 문제였다.

3회차

예제는 제대로 동작했으나 틀렸다.
이동 경우가 1 → v1 → v2 → N, 1 → v2 → v1 → N으로 2가지가 있는데 전자만 고려해서 발생한 문제같았다.
수정했지만 예제의 출력까지 틀렸다.
확인해보니 다익스트라를 수행할 때마다 계산하는 거리가 달라지기 때문에 거리 저장하는 리스트를 매번 초기화해줘야 하는데 다익스트라 함수 밖에 작성해서 이전 값이 남는 바람에 발생한 문제였다. 이를 수정하니 해결되었다.

📌 정답 코드

import sys
import heapq

input = sys.stdin.readline

# 최댓값 정의
INF = int(1e9)


# 우선순위 큐로 구현한 dijkstra 정의
def dijkstra(start, end):
    # 최단 경로 거리 저장 리스트 정의
    distances = [INF] * (N + 1)
    queue = []
    # 시작 노드이므로 거리 0
    distances[start] = 0
    heapq.heappush(queue, (0, start))

    while queue:
        # 최단 경로 탐색 시작
        now_distance, now_node = heapq.heappop(queue)
        # 지금 거리가 더 크면 무시
        if distances[now_node] < now_distance:
            continue

        # 연결 노드와 거리 계산
        for next_node, next_distance in graph[now_node]:
            # 누적 거리 계산
            new_distance = now_distance + next_distance
            # 다음 노드까지의 거리가 현재보다 작으면 조건 만족
            if new_distance < distances[next_node]:
                # 거리 추가
                distances[next_node] = new_distance
                # 힙 삽입
                heapq.heappush(queue, (new_distance, next_node))

    # 최종 이동 거리 반환
    return distances[end]


# 입력
N, E = map(int, input().split())

graph = [[] for _ in range(N+1)]

for _ in range(E):
    a, b, c = map(int, input().split())
    # 양방향 그래프이므로 양쪽으로 연결 내용 추가
    graph[a].append((b, c))
    graph[b].append((a, c))

v1, v2 = map(int, input().split())

# 이동 경로마다 dijkstra 수행
# 1 -> v1 -> v2 -> N 이동
distance_start_v1 = dijkstra(1, v1)
distance_v1_v2 = dijkstra(v1, v2)
distance_v2_end = dijkstra(v2, N)

# 1 -> v2 -> v1 -> N 이동
distance_start_v2 = dijkstra(1, v2)
distance_v2_v1 = dijkstra(v2, v1)
distance_v1_end = dijkstra(v1, N)

# 최단 경로 길이 계산
min_distance = min(distance_start_v1 + distance_v1_v2 + distance_v2_end, distance_start_v2 + distance_v2_v1 + distance_v1_end)

# 최단 경로 리스트가 초기값과 동일하면 경로가 없다는 의미이므로 경우에 따라 출력
print(min_distance if min_distance < INF else -1)

결과

✏️ 회고

다익스트라 문제들의 풀이 구조가 비슷해서 이번엔 조금 더 쉽게 접근할 수 있었다. 하지만 여러 조건들을 놓쳐서 많은 시도 횟수가 필요했다.
아직 다양한 문제를 접해보지 않아서 비슷하다고 느끼는 것 같기도 하다. 자만하지 말아야 겠다고 생각하지만, 골드 문제인데도 스스로 풀이를 더 많이 작성할 때마다 자신감이 점점 오르는 것 같다. 방심하지 말고 포기하지 않고 계속 가서 다익스트라 문제를 정복해보고 싶다.