난이도 : 골드 4
유형 : 다익스트라
https://www.acmicpc.net/problem/1753
문제 접근
가중치 그래프와 시작노드를 입력받고,
1번부터 노드개수 번까지 i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력하는 문제.
1-> 1 : 0
1-> 2 : 2
1-> 3 : max(3, 2+4) = 3
1-> 4 : max(3+6, 2+4+6, 2+5) = 7
1-> 5 : INF
로의 최단 경로의 경로값
시작점은 0으로, 경로가 존재하지 않는 경우는 INF로
발그림 미안합니다.
예제를 눈으로 봤을때는 비교해가면서 답을 낼 수 있지만 해당 로직을 알고리즘으로 설계해서 풀려면 다익스트라 알고리즘 에 대한 개념이 필요하다.
다익스트라 알고리즘은
가중치가 음수가 없는 그래프에서 한 정점으로부터의 최단 경로를 구하는 알고리즘이다.
특정 정점에서 다른 모든 정점까지 갈때 필요한 최단경로를 알 수 있게 된다.
알고리즘에선 우선순위큐를 활용해 시작복잡도를 줄인다.
다익스트라의 구현과정은 다음과 같다.
1️⃣ 먼저, 맵을 펼친다
그래프를 인접 리스트(= 어떤 노드에서 어떤 노드로 갈 수 있고, 비용이 얼마인지)를 기준으로 정리한다.
예를 들어, 1번 → 2번 (비용 3) 이라면 1: [(2, 3)] 이런 식으로 정리.
2️⃣ 출발점에 깃발을 꽂는다.
시작 노드를 기준으로, 그곳까지의 거리를 0으로 설정하고 나머지는 전부 "아직 모름"이니까 무한대로 표시한다.
3️⃣ 가장 가까운 노드를 고른다.
지금까지 확인한 것 중에서 가장 거리가 짧은 노드를 고른다.
처음엔 무조건 출발 노드가 선택됨 (거리가 0이니까)
4️⃣ 주변 노드들에게 물어본다
그 노드와 연결된 이웃 노드들에게 묻는다:
“내가 여기까지 오는 데 비용이 X 들었고, 너까지 가는 비용이 Y라면... 너까지 가는 총 비용은 X+Y야. 지금 알려진 것보다 내가 알려주는 게 더 싸니?”
더 싸게 갈 수 있다면 거리 정보를 업데이트해준다!
5️⃣ 그리고 다음으로 싼 노드를 고른다.
이렇게 모든 이웃을 살펴봤다면,
이제까지 등록된 거리들 중 가장 짧은 거리의 노드를 다음 후보로 고른다.
6️⃣ 이 과정을 반복한다
모든 노드를 한 번씩 다 처리하거나,
더 이상 싸게 갈 수 있는 길이 없을 때까지 위 과정을 반복한다
이제 시작점에서 각 노드까지의 최단 거리가 모두 정리되었다!
거리 정보 배열(distance array)을 보면 정답이 보이게 된다.
이 과정을 토대로 1753번을 풀어보겠다.
해답 및 풀이
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값 (10억)
# ------------------------
# 1️⃣ 입력값 받기
# ------------------------
V, E= map(int,input().split()) # 정점 수, 간선 수
start = int(input()) # 시작 정점
# ------------------------
# 2️⃣ 맵을 펼친다: 인접 리스트로 그래프 구성
# ------------------------
graph = [ [] for _ in range(V + 1)]
for _ in range(E):
u, v, w = map(int,input().split())
# u 에서 v로 가는 가중지 w의 간선
graph[u].append((v, w)) # (다음노드, 가중치)
# print(graph) -> [[], [(2, 2), (3, 3)], [(3, 4), (4, 5)], [(4, 6)], [], [(1, 1)]]
# ------------------------
# 3️⃣ 거리 배열 초기화 (처음엔 모두 모름)
# ------------------------
distance = [INF] * (V + 1)
# ------------------------
# 4️⃣ 출발 노드의 거리를 0으로 초기화 해주고, 튜플형태로 (거리, 노드) 최소 큐에 넣기
# ------------------------
distance[start] = 0
queue = []
heapq.heappush(queue,(0, start))
# ------------------------
# 5️⃣ 다익스트라 시작
# ------------------------
while queue:
now_dist, now = heapq.heappop(queue) # 최소큐에서 (거리, 노드) 꺼내기
# 이미 더 짧은 거리로 처리된 적이 있다면 무시
if distance[now] < now_dist:
continue
# ------------------------
# 6️⃣ 다음 노드들에게 물어본다
# ------------------------
for next_node, next_weight in graph[now]:
cost = now_dist + next_weight # 현재 노드까지 거리 + 다음 노드까지 거리
# 더 짧은 거리 발견 시 업데이트
if cost < distance[next_node]:
distance[next_node] = cost
heapq.heappush(queue, (cost, next_node))
# ------------------------
# 7️⃣ 결과 출력
# ------------------------
for i in range(1, V + 1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])아직 다익스트라 첫 문제라 어색하지만 차차 익숙해질 것 같다.
