[알고리즘] Dijkstra's algorithm 2부 - 구현 준비

💡 Introduction
지난 포스트에서는 예시 그래프를 통해 다익스트라 알고리즘 (Dijkstra's algorithm) 이 어떻게 동작하는지 살펴보았다. 이번 포스트에서는 다익스트라 알고리즘을 실제 프로그래밍 언어를 사용하여 구현할 준비를 한다.

💼 그래프의 표현

가장 먼저, 그래프를 어떻게 표현할지 생각해보자. 일단 각 정점들은 변수를 사용하고, 각 정점들과 그 사이의 거리를 다음과 같은 형식으로 표현할 수 있다:

 

(정점 1, 정점 2, 거리)

 

 

그러므로, 지난 포스트에서 사용된 그래프는 중첩 리스트나 배열을 사용하여 다음과 같이 표현할 수 있다:

 

[[A, B, 3], [A, C, 5], [B, D, 4], [C, D, 7]]

 

막상 이 방식은 A, B, C, D 와 같이 문자열 형태로 정점을 나타내면서 동시에 정수로 거리를 나타내야 해서 일관된 데이터 타입을 사용해야 하는 자료 구조는 적합하지 않는다는 생각이 든다. 물론 거리를 나타내는 값도 문자열로 나타낼 수 있지만, 또 다른 문제점은 양방향이 아니라 단방향으로만 거리를 표현할 수 있다는 것이다. (A, B, 3) 이라는 정보는 (B, A, 3) 라는 정보를 함축할 수 없다.

 

그래서 각 정점을 몇 번째인지에 대한 정보로 식별할 수 있게 추상화한 뒤에 중첩 리스트를 사용하여 그래프를 표현했다. 이제 정수만 사용되며, 두 정점 사이의 거리를 계산했을 때 양방향에서 같도록 표현하기가 더 쉬워졌다.

 

[[0, 3, 5, -1], [3, 0, -1, 4], [5, -1, 0, 7], [-1, 4, 7, 0]]

 

리스트 내의 각 리스트의 인덱스는 몇 번째 정점의 정보인지를 나타내고, 중첩된 리스트에서의 인덱스는 정점에서 다른 몇 번째 정점과의 거리인지를 나타낸다. 위 중첩 리스트의 0번째 인덱스(정점 A)의 리스트 [0, 3, 5, -1] 의 의미는 다음과 같다:

 

A 와 A 사이의 거리는 0이다. (첫 번째 (0번째 인덱스 = A까지의 거리) 0)
A 와 B 사이의 거리는 3이다. (두 번째 (1번째 인덱스 = B 까지의 거리) 3)
A 와 C 사이의 거리는 5이다. (세 번째 (2번째 인덱스 = C 까지의 거리) 5)
A 와 D 사이의 거리는 존재하지 않는다. (네 번째 (3번째 인덱스 = D 까지의 거리) -1)

 

이처럼 정점들 사이에 거리가 없는 것은 -1로 표현한다. 중첩된 리스트의 길이는 정점의 갯수와 같다.

 

📝 그 외 필요한 자료 구조들

다양한 자료 구조들을 사용할 수 있겠지만, 그 중 가장 적합한 자료 구조는 사용되는 맥락과 용도를 고려해서 결정된다. 이제 다른 정보들을 저장하는 자료 구조들에는 무엇이 사용되어야 하고, 어떻게 사용할 것인지 생각해보자.

 

나머지 알아야 할 정보들과 각 정보가 저장될 수 있는 방식을 정리해보면 아래와 같다:

 

알아야 되는 정보	저장되는 방식
시작점으로부터 모든 정점까지의 거리들 각각의 값	int[] dist 보다는 List<Integer> dist: 변동이 잦기 때문이다.
현재 방문 중인 정점 값	int current : 정점이 몇 번째인지에 대한 인덱스로 저장한다.
지금까지 방문되어진 모든 정점들의 값	List<Integer> visited: 마찬가지로 변동이 잦다.
아직까지 방문되지 않은 모든 정점들의 값	List<Integer> unvisited: 변동이 잦다.

 

막상 작성해보니, 방문되어진 정점들과 방문되어지지 않은 정점들의 정보는 하나로 합칠 수 있겠다는 생각이 들었다. 어차피 정점은 인덱스 값을 통해 파악하므로, 불린 리스트를 선언해 처음에는 모두 방문되어지지 않았다는 의미에서 모든 인덱스의 값을 false 로 초기화하고, 이후 N번째 정점이 방문되었으면 리스트의 N번째를 true로 바꾸는 방식을 사용할 수 있다. 그래서 표의 맨 아래 두 셀을 합쳐 아래와 같이 변경하였다.

알아야 되는 정보	저장되는 방식
지금까지 방문되어진 / 방문되지 않은 모든 정점들의 값	List<Boolean> visitedInfo

 

🧱 동작 원리

 

지금까지 정리한 바에 의하면, 알고리즘을 구현하는 메서드는 다음과 같은 특징을 가진다:

 

• 중첩 리스트를 매개변수로 받는다.
• visitedInfo 리스트에서 각 원소를 중첩 리스트에 명시된 정보에 따라 방문하면서 true 로 바꾼다.
• current 에는 현재 방문 정점의 인덱스를 할당한다.
• dist 리스트는 현재 원소와 잠재적으로 바뀔 수 있는 원소의 크기 비교를 통해 업데이트 여부가 결정된다.

 

📌 결론

이제 저번 포스트에서 설명한 단계에 따라 다익스트라 알고리즘을 구현해보자.

다음 포스트에서는 다익스트라 알고리즘을 실제 프로그래밍 언어로 구현해본다.