BOJ(백준) 1753[최단경로]

이번 글에서는 백준 1753번 문제인 “최단경로” 문제를 함께 해결해 보겠습니다. 이 문제는 그래프에서 특정 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 문제로, 다익스트라 알고리즘을 사용하여 해결할 수 있습니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/1753

 

1. 문제 설명

 

1) 문제 개요

주어진 그래프에서 특정 시작 정점에서 다른 모든 정점으로의 최단 경로를 찾는 문제입니다. 그래프는 방향성과 가중치를 가진 간선들로 이루어져 있으며, 시작 정점으로부터 각 정점까지의 최단 거리를 계산해야 합니다.

 

2) 입력

• 첫 번째 줄: 정점의 수 V (1 ≤ V ≤ 20,000)와 간선의 수 E (1 ≤ E ≤ 300,000)

• 두 번째 줄: 시작 정점 K (1 ≤ K ≤ V)

• 다음 E개의 줄: 각 간선 정보를 나타내는 세 정수 u, v, w (u에서 v로 가는 가중치 w인 간선)

 

3) 출력

• 시작 정점 K로부터 다른 모든 정점까지의 최단 거리를 출력합니다. 도달할 수 없는 정점의 경우 “INF”를 출력합니다.

 

2. 접근법

1) 입력받기

• 빠른 입력을 위해 sys.stdin.readline을 사용합니다.

• 그래프를 인접 리스트로 표현하여, 각 정점에 연결된 간선 정보를 저장합니다.

 

2) 다익스트라 알고리즘

• 다익스트라 알고리즘을 사용하여 최단 경로를 찾습니다. 이 알고리즘은 우선순위 큐를 사용하여 구현되며, 각 정점에서 다른 정점으로의 최소 거리를 계산합니다.

• 시작 정점 K로부터 각 정점까지의 거리를 저장하는 리스트를 초기화하고, 처음에는 무한대를 나타내기 위해 큰 값(10^9)을 사용합니다.

• 우선순위 큐에 시작 정점과 그 거리를 넣고, 큐가 빌 때까지 각 정점에서 연결된 간선을 탐색하며 최단 거리를 갱신합니다.

 

3) 결과 출력

• 각 정점의 최단 거리를 1번 정점부터 V번 정점까지 출력합니다. 도달할 수 없는 정점의 경우 “INF”를 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline
from queue import PriorityQueue

V, E = map(int, input().split())    # 정점의 수 V와 간선의 수 E 입력 받음
K = int(input())                    # 시작 정점 K 입력 받음
adj = [[] for _ in range(V+1)]      # 인접 리스트 초기화, 정점 번호는 1부터 시작하므로 V+1 크기로 생성
for _ in range(E):
    u, v, w = map(int, input().split())  # 간선 정보 입력 받음: u에서 v로 가는 가중치 w인 간선
    adj[u].append((v, w))                # 인접 리스트에 간선 정보 추가

pq = PriorityQueue()        # 우선순위 큐 생성
dist = [0] + [10**9] * V    # 거리 리스트 초기화, 무한대를 나타내기 위해 큰 수(10**9) 사용

dist[K] = 0     # 시작 정점 K의 거리를 0으로 설정
pq.put((0, K))  # 시작 정점을 우선순위 큐에 삽입

while pq.qsize() > 0:   # 큐가 빌 때까지 반복
    w, u = pq.get()     # 큐에서 가장 짧은 거리를 가진 정점 꺼내기

    for v, w1 in adj[u]:            # 현재 정점 u에서 이동할 수 있는 모든 정점 v에 대해
        if dist[v] > dist[u] + w1:  # 기존 거리보다 현재 경로를 통한 거리가 더 짧다면
            dist[v] = dist[u] + w1  # 거리 갱신
            pq.put((dist[v], v))    # 갱신된 거리와 정점을 큐에 삽입

for i in range(1, V+1):             # 1번 정점부터 V번 정점까지 거리 출력
    if dist[i] == 10**9:            # 무한대 거리라면 도달할 수 없는 정점이므로
        print('INF')                # 'INF' 출력
    else:
        print(dist[i])              # 도달 가능한 거리 출력

 

4. 코드 설명

1) 입력 받기

• 그래프의 정점 수 V와 간선 수 E를 입력 받음

• 시작 정점 K를 입력 받음

• E개의 간선 정보를 입력 받아 인접 리스트로 저장

2) 초기화

• 거리 리스트 dist를 무한대 값으로 초기화, 시작 정점 K의 거리를 0으로 설정

• 우선순위 큐에 시작 정점과 거리를 추가

3) 다익스트라 알고리즘 실행

• 큐가 빌 때까지 반복

• 큐에서 최단 거리를 가진 정점 u와 그 거리를 꺼냄

• 정점 u에 인접한 모든 정점 v에 대해 거리 갱신 시도

• 만약 dist[v] > dist[u] + w (기존 거리보다 현재 경로가 짧다면)

• dist[v] 갱신

• 큐에 갱신된 거리와 정점 v 추가

4) 결과 출력

• 거리 리스트에서 각 정점의 최단 거리를 출력

• 도달할 수 없는 정점은 “INF”로 출력

 

[순서도]

 

5. Github으로 확인

coTest/BOJ/BOJ01_09_04_1753.py at main · pcy4196/coTest