다익스트라 알고리즘

정점간에 이동비용이 정해져있고 출발지부터 목적지까지 최소 비용을 구하려면 어떻게 해야할까?

 

이 고민을 해결해줄 알고리즘이 다익스트라 알고리즘이다.

 

이 알고리즘은 출발 정점으로부터 나머지 정점들로의 최단거리(최소 비용)를 구할 수 있게 해준다!!

동작 방식

다익스트라 알고리즘은 다음과 같이 작동한다.

 

1) 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하난 선택해 방문한다.

2) 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

 

맨 처음에는 시작점으로의 거리만 0이고 나머지는 다 거리를 무한으로 준다. 그리고 정점 i, j 사이의 거리를 d, 거리 테이블을 dist라고 해보자.

 

다익스트라 알고리즘

dist

1	2	3	4	5	6
0	INF	INF	INF	INF	INF

1번에서 바로 갈 수 있는 인접한 정점은 2, 3, 6번 정점이다. 그리고 1번을 통해 k번 정점으로 가는 거리는 dist[1] + d[1][k] (1에서 k로 가는 비용)이다.

이게 만약 dist[k]보다 작다면 dist[k]가 갱신된다.

지금은 0번을 제외한 모든 정점으로의 dist 값이 무한대이므로 무조건 갱신된다.

1	2	3	4	5	6
0	7	9	INF	INF	14

그 다음, 아직 방문하지 않은 정점 중 비용이 제일 적은 곳이 2번이므로

2번 정점을 방문하여 인접한 3, 4번 정점의 거리 갱신을 시도한다.

1번은 이미 방문했으므로 방문하지 않을것이다. 여기서 3번 정점의 경우는 거리가 갱신되지 않는다!

dist[3]이 이미 dist[2] + d[2][3]보다 작거나 같기 때문이다.

 

dist[3] < dist[2] + d[2][3]

9(1→3) ≤ 7(1→2) + 10(2→3) ⇒ 갱신 x

 

그리고 4번 정점의 경우, 2번 정점에서 비용이 15임으로 INF보다 작기 때문에 갱신된다.

dist[2] + d[2][4]

7 + 15 = 22 ⇒ 갱신

1	2	3	4	5	6
0	7	9	22	INF	14

이렇게 각 정점으로의 비용을 비교해가면서 작은 값으로 갱신시켜주면 된다.

…

최종 dist

1	2	3	4	5	6
0	7	9	20	20	11

이렇게 마지막으로 5번 정점만 남았을 때는 나머지 정점을 다 방문한 상태이므로 아무것도 하지 않게된다.

여기까지가 다익스트라 알고리즘 작동의 과정인데, 이게 끝나고 나면 각 dist 값이 0번 정점으로부터의 실제 최단 거리가 된다!

---

 

다익스트라 알고리즘을 사용한 문제들을 몇가지 풀어보자!

최소비용 구하기

1916번: 최소비용 구하기

1916번: 최소비용 구하기

최소비용 구하기 문제는 정점간의 최소 이동비용을 구하는 대표적인 문제이다!

 

심지어 문제 제목조차 최소비용 구하기다.

 

최소 비용을 구하기 위해서 2중 for문을 사용해서 최소값을 구하게 된다면, O(V^2)의 시간복잡도가 발생하게 될 것이다!

 

이때 도움울 줄 만한것이 우선순위 큐이다.

 

최소 힙을 하나 마련해서 정점 u를 방문해서 인접한 정점 v의 거리를 갱신할 때마다 최소 힙에 (dist[v], v) 쌍을 넣으면 된다. dist 값이 작으면 작을수록 우선순위 큐에서 먼저 나 올 것이다.

 

그 다음 dist 값이 제일 작은 걸 뽑아서, 그 두 번째 인자인 정점 번호를 사용하면 된다.

 

코드

# 최소비용 구하기
# 다익스트라
import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]

# 출발지로부터 해당 정점까지 최소비용을 저장
dist = [sys.maxsize] * (n+1)
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))

st, en = map(int, sys.stdin.readline().split())

def bfs(v):
    pq = []
	# 시작 정점의 비용은 0
    dist[v] = 0
	# 비용과 정점을 저장
    heappush(pq, (0, v))

    while pq:
      # 인접 정점들중 비용이 최소인 정점을 선택
        w, cur = heappop(pq)

      # 이미 방문한 정점은 거리가 갱신되어있다.
        if dist[cur] < w: continue
        
        for wei, next in graph[cur]:
		  # 인접노드들의 비용을 갱신 
            cost = dist[cur] + wei
            if dist[next] > cost:
                dist[next] = cost
                heappush(pq, (cost, next))
bfs(st)
print(dist[en])

• 따로 방문 표시를 위한 배열은 생성하지 않았다.
  • 우선순위 큐의 특성상 비용이 적은 (비용, 정점) 쌍이 먼저 처리된다. 그래서 방문한 정점은 비용이 먼저 갱신되어있다.
  • ex) 1 → 5, 10의 비용(10, 5) 쌍이 최소힙에 들어가 있다. 비용이 커서 우선순위가 매우 밀린다. 하지만 1 → 4 → 5 는 4의 비용이든다.
  • 동일하게 1에서 출발해 5로 도착하는 탐색이지만, 우선순위 큐에의해서 4의 비용쌍이 먼저 처리되어 dist[5]를 갱신시켜 둔다.때문에 이 문장으로 인해 우선순위 큐 뒤에 저장되있던 (10, 5)는 자기 차례가 오면 무시된다.

if dist[cur] < w: continue

---

미로만들기

2665번: 미로만들기

2665번: 미로만들기

미로 탐색문제와 달리 이 문제는 벽이 가로막고있는 상태가 존재하므로 단순히 bfs를 사용해선 끝 방까지 도착하지 못한다.

 

이때 다익스트라 알고리즘을 사용하면 끝 방까지 도달하는데 최소한의 방을 흰방으로 바꾸는 수를 구할 수 있다.

 

기본 아이디어는 이렇다.

 

기본 미로탐색과 동일하게 bfs로 미로를 탐색한다. 이때 흰방을 탐색하고있다면 비용을 0으로 준다.

 

하지만 검은방을 만났다면 비용을 + 1 해준다.

 

이 로직이 중요한데, 검은방이 계속 나온다면 비용은 + 1이 계속 붙을 것이고, 우선순위 큐에서 뒤로 한참 밀리게 된다.

 

때문에 흰방들들을 모두 탐색하고 검은방에 가로막혀있는 상태라면 그제서야 비용이 작은 순서대로 처리된다.

 

이 때 검은 방에 인접한 방들이 흰 방이면 그 방들은 비용이 기존 비용에(검은방을 지났을 때) + 0 으로 저장될 것이므로 다시 흰방들을 bfs로 탐색하게 될 것이다.

 

마지막으로 (n, n)에 도달했을 때 탐색이 종료된다.

 

코드

# 미로 만들기
import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]

# 시작위치를 입력으로 받는다.
def dij(x, y):
    hq = []
    
    # 이동할 방향을 저장
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # 방문 표시를 위한 visted
    visited = [[False] * n for _ in range(n)]

    # 시작 위치와 비용을 힙에 넣는다.
    heappush(hq, (0, x, y))
    while hq:
        w, cx, cy = heappop(hq)

        # 미로 끝을 마주했을 때 비용을 리턴
        if cx == n - 1 and cy == n - 1:
            return w

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                
                if graph[nx][ny] == 0:
                    heappush(hq, (w + 1, nx, ny))
                else:
                    heappush(hq, (w, nx, ny))
                visited[nx][ny] = True

print(dij(0, 0))