DFS 알고리즘 개념 파이썬 코딩테스트 (9)

목차

---

서론

BFS를 넘어 DFS에 대해서 알아보려고 한다. BFS에 대한 내용이 궁금하다면 이 포스팅으로 가길 바란다. 아마 BFS를 모른다면 이 포스팅에서 다루는 DFS를 이해하기 쉽지 않을 것이다. 둘은 뗄레야 뗄 수 없는 사이기 때문이다. DFS 내용에 앞서 DFS, BFS 두 알고리즘의 큰 차이를 말하자면, 전자는 깊이를 우선으로 하는 것이고 후자는 너비를 우선으로 하는 것이다. D는 Depth의 D요, B는 Breadth의 B이기 때문에.

---

DFS 기본 설명

우선 과정 측면에서 BFS와의 차이는 BFS는 deque(내지 queue)로, DFS는 stack으로 한다는 차이가 있다. 위에서 깊이를 우선으로 한다라고도 말했고, 자료구조의 차이를 말했지만 사실 이걸 바로 와닿는건 쉽지 않다. 앞 포스팅에서 BFS는 Best Friend Search 이렇게 말했었다. DFS는 뭐랄까..BFS처럼 딱 철자까진 같진 않아도. Deep friend search정도.. 라고 하면 와닿으려나 모르겠다. 친구를 사귈 때 한놈만 깊게 파는 거다. 최선을 다해서 친해지는것이다. 그러다가 안맞는다? 그럼 이제 다른 친구를 찾고. 다시 그 친구를 깊게 사귀고.. 뭐 그런 방식이라고 보면 된다. 앞 포스팅에서 언급했는 지 모르겠지만 DFS를 미로 찾기에서 쓰면 주옥되는 이유도 바로 이것이다. 한놈만 깊게 파다가 끝을 봤는데 돌아오기 까마득하다면.. 그리고 다시 옆을 갔는데 또 사실 그 길이 아니라 까마득하다면..? 가라가라갇혀 확갇혀 미로에갇혀 확갇혀가 되는것이다.

---

DFS

강의에 나온 코드는 다음과 같다. 보면 BFS 코드와 상당히 흡사하다는 걸 볼 수 있다. stack이 사용된걸 제외하면 말이다. 원소 하나를 빼고 주변을 돈다는 것은 똑같기 때문에 그렇다. 하지만 저 stack과 queue의 차이로부터 방문 순서가 크게 달라진다. BFS는 점점 퍼저가는 식이고(시작점 기준 거리 순으로 방문), DFS는 위에 언급했다시피 깊게 한놈만 판다. 막힐 때 까지 직진하는 것이다. 이러한 차이로 이전 칸 기준 +1을 하는 과정이 있는 거리측정 문제에서는 BFS를 사용하는 것이 다.