백준 - 1916번 최소비용 구하기 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

🔷 알고리즘 분류 - 그래프 이론, 데이스크트라, 최단경로

난이도 - 골드 5

데이크스트라 알고리즘(Dijkstra's algorithm)은 그래프에서 노드 간의 최단 경로를 찾는 알고리즘입니다. 

 

이 알고리즘은 가중치가 양수인 방향 그래프에서 사용됩니다.

파이썬에서 데이크스트라 알고리즘을 구현하려면, 먼저 그래프를 표현해야 합니다. 

 

그래프는 보통 인접 리스트나 인접 행렬로 표현됩니다. 

 

그리고 우선순위 큐를 사용하여 다음으로 탐색할 노드를 결정합니다.

아래는 파이썬에서 데이크스트라 알고리즘을 구현한 예제입니다.

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

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

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:  # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        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(q, (cost, i[0]))

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

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

🔶문제 풀이 - 데이스크트라를 이용한 풀이

import sys
import heapq
input=sys.stdin.readline  # 입력을 빠르게 받기 위해 sys.stdin.readline을 사용

n=int(input())  # 노드의 개수 입력
m=int(input())  # 간선의 개수 입력
INF=float('inf')  # 무한을 의미하는 값으로 float('inf')를 사용
graph=[[] for _ in range(n+1)]  # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
distance=[INF]*(n+1)  # 최단 거리 테이블을 모두 무한으로 초기화
for _ in range(m):
    x,y,z=map(int,input().split())  # x에서 y로 가는 비용이 z라는 간선 정보 입력
    graph[x].append((y,z))  # 그래프에 간선 정보 추가
    
start,end=map(int,input().split())  # 시작 노드와 끝 노드 입력

def dijkstra(start):
    queue=[]  # 우선순위 큐를 위한 리스트 생성
    heapq.heappush(queue,(0,start))  # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    distance[start]=0  # 시작 노드의 최단 거리는 0
    while queue:  # 큐가 빌 때까지
        a,b=heapq.heappop(queue)  # 가장 최단 거리가 짧은 노드와 그 거리 정보 꺼내기
        if distance[b]<a:  # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            continue
        for i in graph[b]:  # 현재 노드와 연결된 다른 인접한 노드들을 확인
            cost=a+i[1]  # 현재 노드를 거쳐서 다른 노드로 이동하는 거리
            if cost<distance[i[0]]:  # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
                distance[i[0]]=cost  # 최단 거리 업데이트
                heapq.heappush(queue,(cost,i[0]))  # 우선순위 큐에 새로운 거리와 노드 정보 추가
                
dijkstra(start)  # 다익스트라 알고리즘 수행
print(distance[end])  # 시작 노드에서 끝 노드까지의 최단 거리 출력

🔶문제 이해하기

아래의 코드를 예시를 통해 이해해 보겠습니다.

 

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

 

1. 시작 노드인 1번 노드의 최단 거리를 0으로 설정하고, 큐에 넣습니다. 그 외의 노드들의 최단 거리는 모두 무한대로 초기화됩니다.

distance: [0, INF, INF , INF , INF ]
queue: [(0, 1)]

2. 우선순위 큐에서 가장 거리가 짧은 노드를 꺼냅니다.

 

처음에는 1번 노드만 들어있으므로 1번 노드를 꺼내게 되고, 1번 노드의 인접 노드들에 대해 거리를 갱신합니다.

distance: [0, 2, 3, 1, 10]
queue: [(1, 4), (2, 2), (3, 3), (10, 5)]

3. 다시 우선순위 큐에서 가장 거리가 짧은 노드를 꺼냅니다.

 

이번에는 4번 노드가 꺼내지게 되고, 4번 노드의 인접 노드에 대해 거리를 갱신합니다.

distance: [0, 2, 3, 1, 3]
queue: [(2, 2), (3, 3), (3, 5), (10, 5)]

4. 다시 우선순위 큐에서 가장 거리가 짧은 노드를 꺼냅니다.

 

이번에는 2번 노드가 꺼내지게 되고, 2번 노드의 인접 노드에 대해 거리를 갱신합니다.

 

하지만 4번 노드의 거리는 이미 1로 갱신되어 있으므로 거리가 갱신되지 않습니다.

distance: [0, 2, 3, 1, 3]
queue: [(3, 3), (3, 5), (10, 5)]

5. 위의 과정을 반복하면, 최종적으로 우선순위 큐가 비게 됩니다.

distance: [0, 2, 3, 1, 4]
queue: []

따라서, 1번 노드에서 5번 노드까지의 최단 거리는 4가 됩니다. 이는 1 -> 3 -> 5 루트를 통해 이동하면 되는 경로입니다.