💻 백준 1916번: 최소비용 구하기

문제 소개 🧐

N개의 도시와 M개의 버스 노선이 주어졌을 때, 특정 출발 도시에서 도착 도시까지 가는 최소 버스 비용을 구하는 문제였다. 도시 번호는 1부터 N까지였다.

입력 📝

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다.
셋째 줄부터 M+2줄까지는 버스의 출발 도시, 도착 도시, 비용 정보가 주어진다.
마지막 줄에는 최소 비용을 구할 출발 도시와 도착 도시 번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력 📤

출발 도시에서 도착 도시까지 가는 최소 비용을 출력한다.

제한 ❌

  • 시간: 0.5초
  • 메모리: 128 MB

나의 풀이: 다익스트라 알고리즘 활용 🎉

Idea

최소 비용을 구하는 문제였기에 다익스트라(Dijkstra) 알고리즘을 사용하기로 했다. 우선순위 큐를 활용하여 현재까지의 최단 거리가 가장 짧은 노드를 선택하고, 해당 노드를 거쳐 다른 노드로 가는 비용을 갱신하는 방식으로 구현했다.

Code

import sys
import heapq

# 입력을 빠르게 받기 위한 설정
input = sys.stdin.readline
INF = float('inf')

# 도시의 개수(n), 버스의 개수(m)
n = int(input())
m = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for _ in range(n + 1)]

# 모든 버스 정보를 입력받기
for _ in range(m):
    v1, v2, w = map(int, input().split())
    # v1번 노드에서 v2번 노드로 가는 비용이 w라는 의미
    graph[v1].append((v2, w))

# 출발 도시와 도착 도시
start, end = map(int, input().split())

# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

def dijkstra(start_node):
    # 우선순위 큐(힙) 사용
    pr_que = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    heapq.heappush(pr_que, (0, start_node))
    distance[start_node] = 0

    while pr_que:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(pr_que)

        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue

        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(pr_que, (cost, i[0]))

# 다익스트라 알고리즘 수행
dijkstra(start)

# 도착 도시까지의 최단 거리 출력
print(distance[end])

Result

성공! ✅

다익스트라 알고리즘을 통해 최소 비용을 성공적으로 찾아냈다.

배운 점 및 느낀 점 ✍️

  • 다익스트라 알고리즘의 이해: 최단 경로를 찾는 대표적인 알고리즘인 다익스트라를 직접 구현하며 그 동작 원리를 깊이 이해할 수 있었다. 특히 우선순위 큐를 활용하는 것이 핵심이었다.
  • 그래프 표현: 인접 리스트를 사용하여 그래프를 효율적으로 표현하는 방법을 다시 한번 확인했다. 노드의 개수가 많고 간선의 개수가 적을 때 유용하다.
  • 무한대 값 설정: 초기 최단 거리를 무한대로 설정하고 갱신하는 과정에서 float('inf')를 사용하는 것이 파이썬에서 편리하다는 것을 알았다.
  • 시간 복잡도: 다익스트라 알고리즘은 일반적으로 O(E log V)의 시간 복잡도를 가진다. 여기서 E는 간선의 수, V는 노드의 수이다. 이 문제의 제약 조건 내에서 충분히 효율적인 풀이였다.
  • 문제 해결 전략: 최단 경로 문제는 다익스트라, 벨만-포드, 플로이드-워셜 등 다양한 알고리즘이 있지만, 문제의 특성(음수 간선 유무, 모든 쌍의 최단 경로 등)에 따라 적절한 알고리즘을 선택하는 것이 중요하다고 느꼈다.