출처 - 이것이 코딩테스트다 with Python
다익스트라
그래프에서 여러 개의 노드가 있을 때, 특저한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
다익스트라 알고리즘은 "음의 간선"이 없을 때 정상적으로 동작한다.
다익스트라 최단 경로 알고리즘은 기본적으로 "그리디 알고리즘"으로 분류된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.
알고리즘 원리
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 3번과 4번을 반복한다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리'정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.
1. 구현은 쉽지만 느리게 동작하는 코드
#무한대 값을 설정
INF = int(1e9)
#노드와 간선의 개수 입력 받기
n,m = map(int,input().split())
start = int(input())
#다익스트라를 위해 필요한 자료구조
graph=[[] for i in range(n+1)] #인접리스트
visited=[False]*(n+1) #방문 확인 리스트
distance=[INF]*(n+1) #최단 거리 테이블
#모든 간선 정보 입력받기
for i in range(m):
a,b,c = map(int,input().split())
graph[a].append([b,c]) #단방향 그래프, a->b까지의 거리가 c임을 저장한다.
def smallest_node():
min_val = INF
idx=0
#테이블에서 가장 작은 값을 가진 and 방문하지 않은 노드를 선택
for i in range(2,n+1):
if min_val>distance[i]:
if visited[i]==False:
min_val=distance[i]
idx=i
return idx
#다익스트라
def dijkstra(start):
#출발노드 초기화
visited[start]=True
distance[start]=0
#start에서 갈 수 있는 노드의 distance를 갱신
for i in graph[start]:
distance[i[0]] = i[1]
#시작 노드를 제외한 n-1번의 탐색을 반복한다.
for i in range(n-1):
node = smallest_node() #노드 선택
visited[node] = True #방문 확인
for j in graph[node]:
cost = distance[node]+j[1] #node를 거쳐서 목적지로 가는 비용을 먼저 계산
if distance[j[0]]>cost: #만약 거쳐 가는 게 더 적은 비용이 든다면
distance[j[0]] = cost #비용을 바꿔준다.
dijkstra(start)
#1번 노드에서 모든 노드로 가는데 걸리는 비용을 출력한다.
for i in range(1,n+1):
if distance[i]==INF:
print("INF")
else:
print(distance[i])책에 나온 탐색 과정을 그대로 코드로 옮기면 이러한 코드를 짤 수 있다.
이 때 n-1번의 탐색을 반복, 최소비용을 가진 노드를 탐색하는데 O(n)이 걸리기 때문에 총 O(n^2)의 시간복잡도를 갖게 된다.
문제점
전체 노드의 수가 5000개 이하라면 문제가 없지만 10000개가 넘어가는 문제가 주어지면 이 코드로는 문제를 해결하기가 어려워진다.
2. 개선된 다익스트라 알고리즘
최단거리 테이블을 선형적으로 탐색하는 부분을 수정하면 시간복잡도를 줄일 수 있다.
=> 우선순위 큐, 힙의 사용!
(힙 설명은 다음 게시글에 추가 설명..^^)
최소힙을 사용하면 탐색할 필요없이 자체적으로 거리가 가장 짧은 데이터를 맨 앞으로 두기 때문에 시간복잡도를 줄여줄 수 있다. O(logN)
import heapq
#무한대 값을 설정
INF = int(1e9)
#노드와 간선의 개수 입력 받기
n,m = map(int,input().split())
start = int(input())
#다익스트라를 위해 필요한 자료구조
graph=[[] for i in range(n+1)] #인접리스트
distance=[INF]*(n+1) #최단 거리 테이블
#모든 간선 정보 입력받기
for i in range(m):
a,b,c = map(int,input().split())
graph[a].append([b,c]) #단방향 그래프, a->b까지의 거리가 c임을 저장한다.
#다익스트라
def dijkstra(start):
q=[]
#출발노드 초기화
distance[start]=0
heapq.heappush(q,(0,start)) #distance, node
while q:
dist, node = heapq.heappop(q) #노드 선택
if distance[node] < dist: #이미 방문했었던 노드라면 무시
continue
for i in graph[node]:
cost = dist+i[1] #노드를 거쳐갔을 때의 비용
if cost<distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
dijkstra(start)
#1번 노드에서 모든 노드로 가는데 걸리는 비용을 출력한다.
for i in range(1,n+1):
if distance[i]==INF:
print("INF")
else:
print(distance[i])smallest_node()함수의 사용이 필요없어졌다.
3. 문제풀이 - 4485번 녹색 옷 입은 애가 젤다지?
링크 - https://www.acmicpc.net/problem/4485
import heapq
import sys
input = sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1] #상하좌우
INF=int(1e9)
def dijkstra():
q=[]
heapq.heappush(q,(graph[0][0],0,0))
while q:
dist,x,y = heapq.heappop(q) #최소 값을 가진 인덱스 pop
if x==n-1 and y==n-1:
print("Problem {0}: {1}".format(count,distance[x][y]))
for i in range(len(dx)):
nx = x+dx[i]
ny = y+dy[i] #상하좌우
if 0<=nx<n and 0<=ny<n: #행렬 범위 체크
cost = dist+graph[nx][ny] #(x,y)노드 거쳐서 (nx,ny)에 갈 때
if distance[nx][ny] < dist: #이미 방문했었던 노드라면 무시
continue
if cost<distance[nx][ny]:
distance[nx][ny] = cost
heapq.heappush(q,(cost,nx,ny))
count=1
while True:
n = int(input()) #행렬의 크기
if n==0:
break
graph = []
distance=[[INF]*n for i in range(n)] #2차원 거리 배열
#그래프 입력받기
for i in range(n):
line = list(map(int,input().split()))
graph.append(line)
#다익스트라 수행
dijkstra()
count+=1개선된 다익스트라 알고리즘 + 그래프 탐색을 사용하여 풀었다.
개념을 그대로 이용하면 되는 문제였다. Good^^
