DFS
깊이우선탐색(DFS)은 방문해야 될 곳이 존재할 때 해당 지점을 우선해서 방문하여 새롭게 탐색을 진행한다. 위 과정을 더 이상 방문할 곳이 없는 곳에 도달할 때까지 반복하는데, 만약 새로운 탐색에서 더 이상 방문할 곳이 없었다면 다시 돌아와 잠시 중단했던 이전 탐색을 재진행한다.
(탐색과 방문은 다르다. 탐색을 한다는 것은 방문을 한다는 것이 아니라 우선은 방문을 할지, 하지 않을지 검사하고 방문해야 되는 곳이었다면 방문으로 이어지는 전체로직자체를 말하는 것)
즉 따라갈 수 있는 곳까지 따라가보고 더 이상 따라갈 곳이 없는 경우, 이전의 갈림길로 다시 돌아가 남은 길을 다시 따라간다는 것이 DFS 탐색의 로직이다.
위상정렬(의존성 그래프)
이러한 DFS의 탐색방식은 의존성이 존재하는 그래프를, 의존성 순으로 탐색해야 할 때 유효하게 사용할 수 있다.
(의존성 그래프는 정점들끼리의 의존성이 정해져있는 그래프로 특정 정점을 방문하기 전 해당 정점이 의존하고 있는 점을 우선해서 방문하는 것을 원칙으로 삼는다. 그리고 의존성그래프를 의존성 순서대로 방문이 진행되도록 구현한 것을 위상정렬이 부른다)
더 이상 방문할 곳이 없는 정점을 발견할 때까지 방문을 진행한다는 DFS의 특성상, 항상 탐색이 먼저 종료되는 정점은 의존성이 가장 떨어지는 정점이 될 수밖에 없다.
따라서 DFS로 먼저 탐색이 종료되는 정점들을 따로 보관하여 나열해간다면, 정점들은 의존성의 역순으로 쌓이게 될 것이다. DFS 만으로 훌륭하게 위상정렬을 표현할 수 있다.
이때 의존성 그래프는 사이클이 존재하지 않는다는 특성으로 인해 이미 방문한 정점들은 굳이 다시 방문할 필요가 없으므로 방문을 스킵 해주는 구현이 들어간다는 특징이 있다.
오일러 서킷(한붓그리기)
오일러서킷(한붓그리기)을 탐색하는 알고리즘 역시 DFS로 구현이 가능하다.
오일러서킷이란 존재하는 모든 간선을 정확히 1번씩만 지나면서 다시 시작점으로 돌아오는 경로를 말한다. (오일러경로(트레일)의 경우는 경로가 반드시 시작점으로 다시 돌아올 필요는 없고, 모든 간선을 정확히 1번씩만 지나면 된다)
따라서 오일러서킷의 탐색을 구현하는 경우에는 정점보다는 간선에 더 집중한다.
한 번도 따라가지 않았던 간선이 존재한다면 해당 간선을 따라간다. 해당 과정에서 이미 방문해봤던 정점에 방문하게 되더라도 따라가본다.
그리고 더 이상 따라갈 수 없는 간선이 없다면 다시 갈림길로 되돌아가서 아직 따라가지 않았던 간선을 새로 찾는다.
되돌아가는 과정에서는 지금까지 따라왔던 간선들을 리턴하며 따로 보관한다. 해당 방식으로 모든 간선을 따라가본다면 결국 존재하는 모든 간선을 1번씩만 지나면서 모든 곳을 전부 방문하며 방문순서를 저장할 수 있다.
한번 방문했던 정점을 더 이상 방문하지 않는 위상정렬과는 구현방식이 약간 달라지겠지만, 오일러서킷 역시 본질적으로는 비슷한 느낌이다.
결국 DFS
결국 DFS란 '따라갈 수 있는 곳까지 따라가고 더 이상 따라갈 수 없는 경우, 이전의 갈림길로 다시 돌아가 남은 길을 다시 따라간다'라는 재귀적인 탐색의 로직이다.
이러한 재귀적인 로직을 큰 틀로 삼아 세부적인 구현만을 바꿔서 특정 상황별로 적용되게 만든 것이 위와 같은 오일러 서킷과 위상정렬의 구현이다.
즉 단순하게 오일러서킷은 DFS이고, 위상정렬은 DFS라며 단정 지으며 문제에 접근하는 것보다는, DFS의 로직 자체를 이해하고 해당 로직을 특정된 상황에서 써먹을 수 있을지 없을지, 쓰는 것이 좋을지 좋지 않을지, 판단하는 생각 자체를 기르는 것이 중요해 보인다.
