[백준] 1504 특정한 최단 경로

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

특정 출발점에서 목적지까지 도착하는 최단 경로를 구하기 위하여 다익스트라를 이용하였습니다.

또한, 거리 기록을 최초에 임의의 큰 값을 입력하여 도착 가능한 최단 경로를 구하도록 구성하였습니다.

 

두 지점의 노드를 필수적으로 통과해야 했으므로 '출발지 -> 노드1 -> 노드2 -> 도착지' 또는 '출발지 -> 노드2 -> 노드1 -> 도착지' 의 두가지 경우를 탐색하였습니다.

출발지, 노드1, 노드2 를 시작으로 하는 다익스트라를 세번 이용하였습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')

def solution(start: int):                           # 다익스트라 탐색
    distance = [1e10] * (N+1)                       # 출발지로부터 각 노드까지 거리
    heap = [(0, start)]                             # 최소힙 리스트, 출발점 세팅
    
    while heap:
        dist, node = heapq.heappop(heap)
        if distance[node] > dist:                   # 아직 안가본 길이면, 거기까지 가는 최소 거리 저장
            distance[node] = dist
            for next in linked[node]:
                heapq.heappush(heap, (distance[node] + next[0], next[1]))
    return distance

N, E = map(int, sys.stdin.readline().split())           # 정점의 개수, 간선의 개수
linked = [[] for _ in range(N+1)]                       # 정점들 간에 연결 관계

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())    # 출발 정점, 도착 정점, 두 정점간 거리
    linked[a].append((c, b))                            # 정점 양방향 연결 관계 설정
    linked[b].append((c, a))

necessary = list(map(int, sys.stdin.readline().split()))    # 꼭 방문해야할 정점 리스트

dis_init = solution(1)                                      # 1번 정점에서 각 정점으로의 거리 구함

dis_1 = solution(necessary[0])                              # 꼭 방문할 첫번째 정점에서 다른 정점으로의 거리
dis_2 = solution(necessary[1])                              # 두번쨰 정점에서 다른 정점으로의 거리

# 출발지 -> n1 -> n2 -> 도착지와 출발지 -> n2 -> n1 -> 도착지 중 짧은 거리
ans = min(dis_init[necessary[0]] + dis_1[necessary[1]] + dis_2[N], dis_init[necessary[1]] + dis_2[necessary[0]] + dis_1[N])

# 경로 존재하지 않는다면 -1, 그 외 출력
if ans >= 1e10:
    print(-1)
else:
    print(ans)

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다