길찾기 알고리즘에는 DFS, BFS, 다익스트라, Best-First Search, A* 등 다양한 것이 존재합니다.
그 중 오늘은 DFS와 BFS, 다익스트라에 대해 학습해보겠습니다.
1. DFS (Depth First Search)
DFS는 깊이 우선 탐색이라고 하며, 이름에 걸맞게 어떠한 그래프를 탐색할 때 최대한 깊숙히 탐색을 한 후, 더 탐색할 수 없으면 다른 경로를 탐색하는 알고리즘입니다.
만약 위와 같은 그래프가 있고, 2차원 배열로는 저렇게 표현했다고 합시다.
시작점이 노드 A라고 했을 때, DFS 알고리즘으로 그래프를 순회한다면 어떤 순서로 순회를 할까요?
- DFS의 순회 과정 -
1) A와 연결된 노드는 B와 C 입니다. A는 자신과 연결된 2개의 노드 중 어떤 노드를 선택할 지 고릅니다.
두개의 노드 중 무엇을 선택해도 상관은 없습니다.
저는 노드를 선택해야 할 경우, 그림에서 보았을 때 가장 위쪽에 선택하는 노드를 고르도록 하겠습니다.
▶ 선택된 노드는 "B"입니다.
2) B와 연결된 노드 중 B보다 깊이가 깊은 노드는 D, E 입니다.
저는 그림에서 보았을 때 가장 위쪽에 선택하는 노드 D를 고르겠습니다.
▶ 선택된 노드는 "D"입니다.
3) D와 연결된 노드 중 D보다 깊이가 깊은 노드는 없습니다.
D에서 더 깊이 탐색을 하려고 해도 깊이가 더 깊은 노드가 없기 때문에 다시 B로 돌아옵니다.
4) B와 연결된 노드 중 B보다 깊이가 깊으며 아직 탐색하지 않은 노드는 E입니다.
▶ 선택된 노드는 "E"입니다.
5) E와 연결된 노드 중 E보다 깊이가 깊으며 아직 탐색하지 않은 노드는 F와 G입니다.
저는 그림에서 보았을 때 가장 위쪽에 선택하는 노드 G를 고르겠습니다.
▶ 선택된 노드는 "G"입니다.
6) G와 연결된 노드 중 G보다 깊이가 깊은 노드는 없습니다.
G에서 더 깊이 탐색을 하려고 해도 깊이가 더 깊은 노드가 없기 때문에 다시 E로 돌아옵니다.
7) E와 연결된 노드 중 E보다 깊이가 깊으며 아직 탐색하지 않은 노드는 F입니다.
▶ 선택된 노드는 "F"입니다.
8) F와 연결된 노드 중 F보다 깊이가 깊으며 아직 탐색하지 않은 노드는 없습니다.
F에서 더 깊이 탐색을 하려고 해도 깊이가 더 깊은 노드가 없기 때문에 다시 E로 돌아옵니다.
9) E와 연결된 노드 중 아직 탐색을 하지 않은 노드는 없습니다.
다시 B로 돌아옵니다.
10) B와 연결된 노드 중 아직 탐색을 하지 않은 노드는 없습니다.
다시 A로 돌아옵니다.
11) A와 연결된 노드 중 A보다 깊이가 깊으며 아직 탐색하지 않은 노드는 C입니다.
▶ 선택된 노드는 "C"입니다.
이러한 과정으로 그래프를 순회할 수 있습니다.
이렇게 깊이를 기준으로 탐색을 하는 길찾기 알고리즘을 DFS라고 합니다.
2. BFS (Breadth First Search)
BFS는 너비 우선 탐색이라고 하며, 이름에 걸맞게 어떠한 그래프를 탐색할 때 같은 깊이에 해당하는 노드부터 탐색하고 더 탐색할 수 없으면 더 깊은 노드들을 탐색하는 알고리즘입니다.
방금 DFS에서 사용했던 그래프와 같은 그래프와 2차원 배열입니다.
시작점이 노드 A라고 했을 때, BFS 알고리즘으로 그래프를 순회한다면 어떤 순서로 순회를 할까요?
- BFS의 순회 과정 -
1) A와 연결된 노드는 B와 C 입니다. A는 자신과 연결된 2개의 노드 중 어떤 노드를 선택할 지 고릅니다.
저는 노드를 선택해야 할 경우, 그림에서 보았을 때 가장 위쪽에 선택하는 노드를 고르도록 하겠습니다.
▶ 선택된 노드는 "B"입니다.
2) B와 같은 깊이에 해당하는 노드는 C입니다.
▶ 선택된 노드는 "C"입니다.
3) C와 같은 깊이에 해당하는 노드 중 탐색하지 않은 노드가 없습니다.
더 깊은 곳을 탐색합니다.
4) 다음 깊이에 해당하는 노드는 D, E, F 입니다.
제일 위쪽 노드인 D부터 탐색하겠습니다.
▶ 선택된 노드는 "D"입니다.
5) D와 같은 깊이에 해당하는 노드는 E, F 입니다.
저는 위쪽 노드인 E부터 탐색하겠습니다.
▶ 선택된 노드는 "E"입니다.
6) 남은 노드인 F를 선택합니다.
▶ 선택된 노드는 "F"입니다.
7) F와 같은 깊이에 해당하는 노드 중 탐색하지 않은 노드가 없습니다.
더 깊은 곳을 탐색합니다.
8) 다음 깊이에 해당하는 노드는 G 입니다.
▶ 선택된 노드는 "G"입니다.
이러한 과정으로 그래프를 순회할 수 있습니다.
이렇게 너비를 기준으로 탐색을 하는 길찾기 알고리즘을 BFS라고 합니다.
3. Dijkstra (다익스트라의 최단 경로 알고리즘)
Dijkstra는 네덜란드의 컴퓨터 과학자였던 에츠허르 다익스트라가 고안한 길찾기 알고리즘으로 그의 이름을 따서 지어진 이름입니다. BFS나 DFS와는 달리 이름만 들어서는 무슨 알고리즘인지 감이 잘 안올 것입니다.
Dijkstra 알고리즘은 BFS와 굉장히 유사하며, 노드 사이 간선(Edge)에 양의 가중치를 갖는 그래프(음의 가중치 허용 X)에서 최단 경로를 찾을 때 사용할 수 있습니다.
여기서 가중치는 DFS와 BFS에서는 등장하지 않았던 개념인데 쉽게 생각해서 그 지점까지의 거리라고 보시면 될 것 같습니다.
- Dijkstra의 탐색 과정 -
해당 알고리즘이 동작하는 과정은 아래와 같습니다.
1) 출발지를 선택하고 Distance를 0으로 설정합니다.
2) 출발지와 연결된 노드의 Distance를 업데이트합니다.
3) 현재까지 업데이트된 Distance를 보고 가장 좋은 길(즉, 최단 거리의 길)을 선택합니다.
4) 현재까지 업데이트된 Distance와 이전 단계에서 선택된 노드의 Distance를 업데이트해줍니다.
이때, 이미 Distance가 업데이트된 노드라도 더 짧은 경로가 있다면 업데이트 해주어야 합니다.
5) 현재까지 업데이트된 Distance를 보고 가장 좋은 길(즉, 최단 거리의 길)을 선택합니다.
6) 이전 단계에서 선택된 노드와 연결된 노드가 없다면 선택된 노드 다음으로 짧은 거리인 노드를 선택합니다.
7) 이전 단계에서 선택된 노드와 연결된 노드의 최단 거리를 업데이트해줍니다.
8) 선택되지 않은 노드 중 Distance가 가장 짧은 것을 선택합니다.
9) 이전 단계에서 선택된 노드와 연결된 노드의 최단 거리를 업데이트해줍니다.
10) 선택되지 않은 노드 중 Distance가 가장 짧은 것을 선택합니다.
11) 모든 노드를 확정했다면 탐색을 종료합니다.
오늘 기본적인 DFS, BFS, Dijkstra 알고리즘으로 그래프를 탐색하는 방법에 대해 알아보았습니다.
다음엔 이것을 어떻게 구현하는지에 대해 포스팅하겠습니다.
오늘도 고생 많으셨습니다 :)
'C# 공부 > 알고리즘' 카테고리의 다른 글
| 미로 생성 알고리즘(Binary Tree, Sidewinder) (0) | 2020.08.16 |
|---|
