[알고리즘] 다익스트라(Dijkstra), 그것이 알고싶다

 

안녕하세요

오늘은 그래프에서 가장 짧은 경로를 찾는

최단 경로 알고리즘 중, 다익스트라에 대해서 알아보려고 합니다!

또한, 간단한 문제를 파이썬을 이용해서 같이 풀어봅시다.

---

# 최단 경로 알고리즘이란?

어떤 그래프에서 각각의 간선에 가중치가 있을 때,

특정 노드에서 다른 노드까지 이동하면서 어떤 경로를 이용해야 가장 작은 가중치의 합을 가지는 지를 구하는 문제입니다.

 

이해가 잘 안된다면 예시문제를 한번 보면서 천천히 따라가 볼까요?

백준의 녹색 옷 입은 애가 젤다지? 이 문제를 보면, 링크가 처음 위치부터 목표 지점까지 최소한의 돈을 지불하고 가야합니다.

젤다 문제 첫번째 예제

 

이런식으로 어떤 경로(간선)를 선택하느냐에 따라 목표 지점에 도착했을 때의 가중치 합이 달라지고,

그 때의 최소값을 찾는 문제가 최단 경로 알고리즘이라고 할 수 있습니다.

파랑색으로 가는 것과 빨간색으로 가는 것이 서로 드는 비용이 다름!

 

 

---

 

그럼, 최단경로 알고리즘 중 다익스트라는 뭘까?

우선 다익스트라를 하기 위해서는 우선순위 큐(= 힙)라는 것을 이해해야 합니다.

 

 

# 우선순위 큐란?

우선순위 큐는 말 그대로 우선순위대로 원소를 넣고 빼는 것입니다.

파이썬에서는 우선순위 큐를 간단하게 heapq으로 구현할 수 있습니다.

import heapq

# 힙이 될 배열 생성
pq = []
heapq.heappush(pq, 3) # pq 힙에 3을 넣어줌
heapq.heappush(pq, 1) # pq 힙에 1을 넣어줌

print(pq) # [1, 3]

 

3 → 1 순서대로 넣어줬지만 힙은 작은 순서대로 들어갑니다.

 

 

 

# 다익스트라(Dijkstra)란?

다익스트라 알고리즘은 우선순위 큐를 이용하는 최단 경로 알고리즘입니다.

또는 BFS 알고리즘과 DP 알고리즘을 같이쓰는 느낌으로 생각할 수도 있습니다.

 

위의 젤다 문제를 기준으로 다익스트라를 알아볼까요?

 

우선, 맵과 같은 크기의 coin 행렬을 만들어 줍니다.

각각의 칸에는 각 위치에서 잃는 최소한의 돈을 넣어줄 예정입니다.

coin = [[float('inf') for _ in range(N)] for _ in range(N)]

계속 돌면서 coin의 최소값을 업데이트 해주기 위해 가장 큰 값을 초기값으로 설정해 줍시다!

 

아까 배웠던 힙을 이용해서 전체적인 로직을 짜보면 다음과 같습니다.

import heapq

# 상하좌우 방향
dire = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def dijkstra():
	# 우선순위 큐
    pq = []
    heapq.heappush(pq,(MAP[0][0], 0, 0))	# 처음 위치에서 잃는 돈과 위치를 힙에 넣어줌
    while pq:
        # lose는 지금까지 잃은 돈
        lose, cy, cx = heapq.heappop(pq)
        
        # 만약 지금까지 잃은 돈이, 여기서 구했던 최소값보다 크다면
        if lose > coin[cy][cx]:
            continue	# 계산할 필요가 없음

        for dy, dx in dire:	 # 모든 방향을 확인
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < N and 0 <= nx < N:		# 유효한 위치라면,
                nextlose = lose + MAP[ny][nx]	# 다음에 잃을 돈은 현재 잃은 돈 + 다음 위치에서 잃을 돈
                # 만약 저장되어 있는 잃은 돈보다 지금 구한게 더 적다면, 업데이트를 해줌
                if coin[ny][nx] > nextlose:
                    coin[ny][nx] = nextlose
                    heapq.heappush(pq,(nextlose, ny, nx))
                    
tc = 0
while True:
    tc += 1
    N = int(input())
    # N이 0이 되면 프로그램 종료
    if not N:
        exit()
    MAP = [list(map(int,input().split())) for _ in range(N)]
    
    # 각 위치에서 잃는 최소한의 coin
    coin = [[float('inf') for _ in range(N)] for _ in range(N)]
    dijkstra()
    print(f'Problem {tc}: {coin[N-1][N-1]}')

 

해당 코드를 처음부터 따라가보면 다음과 같습니다.

초기 상태

0,1 위치로 가면 coin이 갱신된다

(1,0) 위치일 때

(1,1) 위치에서 비교 1

(1, 1)  위치에서 비교 2

 

이런식으로 계속해서 coin을 갱신해 나가면,

pq가 비었을 때 coin에 저장되어있는 값은 각 위치에서의 최소값이 되는 것입니다.

 

 

다익스트라 알고리즘은 

✔ 각 노선의 가중치가 음수가 아닐 때에만 사용할 수 있다는 점을 유의해야 합니다.

만약 가중치가 음수가 된다면, 다른 최단경로 알고리즘인 벨만 포드, 플루이드 워셜 등의 알고리즘을 사용해야합니다.

---

오늘은 최단 경로 알고리즘, 그 중에서도 다익스트라에 대해서 알아봤는데요.

유익하셨다면 다음에 또 놀러와주세요!