전 시간에 보았던 이 그래프를 탐색하는 방법에 들어가기 전에, DFS와 BFS를 좀 더 쉽게 이해시켜줄 '이진 트리'를 DFS와 BFS로 탐색해봅시다.
트리 순회 - BFS
더 간단한 BFS먼저 보도록 하겠습니다. 시작 노드는 늘 그렇듯 1번입니다.
BFS의 경우는 너비 우선 탐색이라는 이름에 걸맞게 현재 노드의 자식노드를 전부 행선지에 넣고, 다음 노드에서도 반복하는 방식인데요, 그림으로 한번 보겠습니다.
1번 노드를 방문합니다. 다음 행선지는 2와 3이 되겠네요.
2번 노드를 방문합니다. 마찬가지로 2의 자식인 4와 5를 행선지에 추가합니다.
3번 노드를 방문합니다. 3의 자식은 6과 7을 행선지에 추가합니다. 이후 순차적으로 방문합니다.
한 그림으로 정리하면 다음과 같습니다.
다음과 같이, 1-2-3-4-5-6-7 순으로 방문하는것을 알 수 있습니다.
그런데, 눈치가 빠르신 분들이라면 행선지를 저장하는 자료구조가 큐(queue)인걸 눈치채셨을겁니다.
이 점을 기억하고 DFS로 넘어가보겠습니다.
트리 순회 - DFS
시작 노드는 늘 1번입니다. 1번에서 DFS를 시작하여 다음은 2번 노드를 방문합니다.
2번 노드를 방문했습니다. 그리고 여기서 2번노드를 시작 노드로 하여 다시 DFS를 시작합니다. 그러면 다음 행선지는 4번 노드가 되겠죠?
4번 노드에 방문했습니다. 4번 노드에서 다시 DFS를 시작해야하지만, 4번 노드는 자식이 없습니다. 그러므로 다시 2번 노드로 거슬러 올라갑니다.
2번 노드로 돌아왔지만 2번 노드는 이미 방문했기에 따로 출력하진 않습니다. 단, 이해를 돕기 위해 더 짙은 색으로 칠해주었습니다. 이제 2번 노드의 남은 자식인 5번 노드를 방문합니다.
5번 노드를 방문하여 다시 DFS를 실행해야 하지만 5번 노드는 자식이 없습니다. 2번도 방문할 자식이 더이상 남아있지 않으므로 1번노드까지 거슬러 올라갑니다.
1번 노드로 되돌아와 남은 노드인 3번을 방문합니다. 지금까지 해왔던 식으로 3번에서 다시 DFS를 실행해 6번, 6번에서 3번으로 거슬러 올라와 7번까지 방문하여 탐색을 마칩니다.
불규칙해보이지만 분명한 규칙성이 있습니다. 시작 노드 1번에서 시작하여 더이상 방문할 노드가 없을때까지 자식 노드를 방문하고, 더이상 방문할 노드가 없다면 되돌아가 다른 노드를 방문합니다. 방문한 순서는 1-2-4-5-3-6-7이 되겠네요.그런데, 방식이 '재귀함수'와 비슷하지 않나요? DFS는 재귀함수로 구현할 수 있습니다.(지금은 이해하지 못하셔도 괜찮습니다. 어차피 코드를 보면 이해하실 수 있을테니까요.)
긴 과정이었습니다. 이제 BFS와 DFS가 어떻게 작동하는지 알았으니, 그래프를 한번 순회해보도록 하겠습니다.
그래프 순회 - BFS(큐)
시작노드는 늘 1번입니다. 사실 상관없긴 하지만 그냥 1번으로 합시다. 1번과 인접한 2번 노드를 행선지에 추가합니다.
2번 노드를 방문합니다. 2번과 인접한 3번과 4번 노드를 행선지에 추가합니다. 이때, 주의깊은 분이라면 왜 3번을 먼저 넣냐, 4번을 먼저 넣어도 되는 것 아니냐? 라고 생각하실 수 있습니다. 전 시간에 매트릭스를 만들때, 간선을 기준으로 만들었었죠? matrix[2]에 저장된 값은 [0,1,0,1,1,0,0]이었습니다. 즉, 1번부터 연결되었나 확인한다는 뜻이죠. 당연히 4번보다 3번을 먼저 확인하게 됩니다. 장황하게 설명했지만 결국 노드의 숫자순으로 탐색한다는 것입니다.
3번 노드를 방문합니다. 3과 인접한 노드는 2, 4, 5, 6번이 있지만 2번 노드는 이미 방문했기 때문에 행선지에 추가하지 않습니다. 이후 순차적으로 방문합니다. BFS로 방문한 순서는 1-2-3-4-5-6이 되겠네요.
그래프 순회 - DFS(재귀함수)
시작 노드에서 DFS를 실행합니다. 이 경우에는 인접한 노드인 2번을 방문하겠네요.
2번 노드를 방문하여 DFS를 실행합니다. 3번과 4번이 연결되어있지만 앞서 설명했듯 3번 간선을 먼저 입력했으므로 3번 노드를 방문합니다.
3번 노드를 방문하여 DFS를 실행합니다. 이런식으로 진행하면 1-2-3-4-5-6으로 BFS와 같음을 알 수 있습니다.
그렇다면 왜 이런 일이 발생할까요?
이 그래프가 분기를 하지 않고도 모든 그래프를 순회할 수 있는 그래프라서 그렇습니다. 다시말해, 1번부터 6번까지 가는 과정에서 거슬러 올라갈 일이 없다는거죠. 이해를 돕기 위해, 3-4번 간선과 4-5번 간선을 끊어보겠습니다.
1번 노드, 시작. DFS를 실행하여 2번 노드를 방문합니다.
2번 노드에서 DFS를 실행하여 간선 순으로 3번 노드를 방문합니다. 그 다음 과정은 간단하게 넘기겠습니다.
이렇게 6번 노드까지 방문하였습니다. 이제 6번 노드는 인접한 노드가 없네요. 이제 다시 되돌아갈 차례입니다. 아직 인접한, 방문하지 않은 노드가 남은 2번 노드까지요.
2번 노드까지 되돌아왔습니다. 이제 남은 노드인 4번을 방문합니다.
탐색이 끝났습니다. 1-2-3-5-6-4순으로 방문했죠. DFS는 한 번의 탐색으로 전부 찾지 못할 경우 되돌아가는 일이 생긴다는점을 명심하세요.
번외)스택으로 구현한 DFS
BFS의 행선지를 저장할때, 큐를 사용했습니다. 스택으로 저장하면 어떻게 될까요?(그저 '번외'일 뿐이므로, 나는 이미 충분히 알만큼 알았고 지칠만큼 지쳤다! 하신다면 넘어가셔도 무방합니다.)
1번 노드를 방문하여, 인접한 2번 노드를 저장합니다.
2번 노드를 방문하여, 인접한 3, 4번 노드를 저장합니다. 스택의 경우에는 가장 마지막에 들어간 자료가 제일 먼저 나오므로, 마지막에 들어간 4번 노드를 방문합니다.
4번 노드를 방문하여 인접한 5번 노드를 저장합니다. 단, 3번은 이미 있으므로 다시 저장하지 않습니다. 다음은 5번 노드를 방문하게 되겠네요.
5번 노드를 방문하여 인접한 6번 노드를 저장합니다. 마찬가지로 3번은 저장하지 않습니다.
이렇게 탐색이 끝났습니다. 근데 이번엔 1-2-4-5-6-3으로 순서가 약간 다르게 나왔습니다. 하지만 가능한한 깊게 들어간다는 점에서 DFS의 요건은 충족합니다. DFS는 스택/재귀함수 두 가지 버전으로 구현할 수 있습니다.
정리하겠습니다. DFS와 BFS를 이해하기 위해 트리를 순회하였고, 그 다음은 그래프를 BFS, DFS를 순회해보았습니다. DFS는 두 가지 버전을 살펴보았으며 다음 차시엔 그래프를 BFS, DFS(재귀함수), DFS(스택)으로 순회하는 코드를 짜보겠습니다.
'코딩 > 알고리즘' 카테고리의 다른 글
| [파이썬] DFS와 BFS 3 - 코드 뜯어보기 (0) | 2021.02.09 |
|---|---|
| [파이썬] DFS와 BFS 1 - 그래프를 이중리스트로 나타내기 (0) | 2021.01.28 |
