❓문제
https://www.acmicpc.net/problem/1753
❗문제 정리
다익스트라 알고리즘 연습하기
distance[now] : 현재노드 now까지의 최단 거리
dist : 시작노드 (index)부터 now까지의 거리
cost=dist+i[1] : 시작노드 (index)부터 now까지의 거리+현재노드 now까지의 최단 거리
📑코드
import heapq
import sys
input=sys.stdin.readline
V,e=map(int, input().split())#정점수, 간선수 문제에서 정점수 변수는 대문자 V
INF=int(1e9)
distance=[INF]*(V+1)
#시작정보 입력받기
start=int(input())
#연결노드 정보 담기
graph=[[] for _ in range(V+1)]
for i in range(e):
u, v, w=map(int, input().split())#문제에서 도착지점 변수 소문자 v
graph[u].append((v,w))
def heapq_dijkstra(start):
q=[]
#시작 노드로 가기 위한 최단 경로를 0으로 설정 후 큐에 삽입
heapq.heappush(q,(0,start))
distance[start]=0
while q:#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]))
heapq_dijkstra(start)
for i in range(1,V+1):#distance 길이보다+1커야하는거 잊지마라1
if distance[i]==INF:
print("INF")
else:
print(distance[i])📝코드 설명
import heapq
import sys
input=sys.stdin.readline
V,e=map(int, input().split())#정점수, 간선수 문제에서 정점수 변수는 대문자 V수의 범위가 크기 때문에 힙 다익스트라를 사용해야한다. -> heapq
많은 입력으로 인해 시간초과가 나지 않도록 -> sys
정점수(V), 간선수 (e)를 입력받는다.
INF=int(1e9)
distance=[INF]*(V+1)최단거리 테이블 distance를 만든다.
초기값은 무한으로 넣어주고, 테이블의 크기는 0을 포함한 노드의 개수이기에 n+1크기로 설정한다.
start=int(input())시작노드를 입력받는다.
시작노드가 정해져있기 때문에 플루이드가 아닌 다익스트라로 푼다.
graph=[[] for _ in range(V+1)]
for i in range(e):
u, v, w=map(int, input().split())#문제에서 도착지점 변수 소문자 v
graph[u].append((v,w))노드와 간선의 정보를 입력받아 저장하기 위한 graph를 만들어 준다.
시작 노드를 인덱스로 하여, (도착노드, 거리)값을 넣어준다.
다익스트라 구현하기
def heapq_dijkstra(start):
q=[]
heapq.heappush(q,(0,start))
distance[start]=0- 입력받은 시작 노드를 (거리, 도착노드==시작노드) 로 q에넣어준다.
이때, 시작노드와 도착노드가 같아서 최단거리 테이블에서 거리는 0을 넣어준다.
while q:
dist, now=heapq.heappop(q)
if distance[now]<dist:
continue- q가 비어있지 않을때까지, 1. 큐에 (거리, 도착노드)를 넣기 2. 최단거리 테이블 업데이트를 반복한다.
q에서 거리(dist), 현재노드(now)를 pop해서 빼준다. 이때, q에서는 거리가 오름차순으로 정렬되어있어서 q에서 가장 거리가 짧은 튜플(거리, 도착노드)부터 나온다.
q에서 가져온 거리(dist)가 최단거리 테이블보다 크면 무시한다.--> 그냥 큐에서 빼준 상태
for i in graph[now]:#현재 노드와 연결된 다른 인접한 노드들 확인
cost=dist+i[1]
if cost<distance[i[0]]:#현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
distance[i[0]]=cost
heapq.heappush(q,(cost, i[0]))- 만약, q에서 뽑은 거리가 원래 있던 길이보다 짧아서 최단거리 테이블을 업데이트해야한다면,
q에서 뽑은 도착노드->시작노드로 변경하고 테이블 업데이트.
튜플의 형태가 (도착노드, 거리)기에 최단거리를 업데이트하려면 i의 1번 인덱스를 가져와서 기존 거리와 더해줌. e.g) 3에서 4로 갈때, 3이 가진 최단거리(dist) + 3에서 4로 가는 거리(i[[1])
이후, q에서 pop해서 빼준다.
heapq_dijkstra(start)다익스트라 함수 실행
for i in range(1,V+1):#distance 길이보다+1커야하는거 잊지마라1
if distance[i]==INF:
print("INF")
else:
print(distance[i])노드가 1번부터시작하므로, 1부터 노드 개수+1까지 반복문을 실행시켜, INF인 경우 INF출력, 아닌 경우, 최단거리의 값을 출력한다.
🎖제출 결과
💡insight
문제에서 정점수는 대문자 V, 도착 노드의 변수는 소문자 v로 지정했다 대소문자 구별을 잘하자.
AI dev