[자료구조와 알고리즘] DFS (깊이 우선 탐색)

프로그래머스 깊이/너비 우선 탐색

2학년 1학기, 동아리에서 진행하는 알고리즘 스터디에서 DFS 문제를 선정한 적이 있었다. <여행경로>라는 문제였는데, 많이 헤맸고 결국 일주일 내에 해결하지 못한 것이 기억난다. 그 때 그저 "내 실력이 아직 많이 모자라구나"라고 생각했다. 알고리즘 문제를 풀어본 경험이 적기도 했지만, 알고리즘 공부는 전혀하지 않은 채 무작정 문제만 해결하려고 하니 벅찬 게 당연하다. 그때 풀지 못했던 DFS/BFS 문제를 해결하기 위해 제대로 공부하려고 한다.

DFS와 BFS를 알기전에, 그래프란?

그래프

단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 비선형 자료구조

아주 어려운 말은 아니지만 역시 그림으로 이해하는 것이 빠르다 😋

사진 속 3가지 종류 모두 그래프로, 다양한 형태를 가질 수 있다. 우리가 잘 알고있는 트리 또한 그래프 중 하나이며, 특별한 케이스이다. 즉, 그래프는 연결된 객체 간의 관계를 표현하는 자료구조라고 할 수 있겠다. 방향 그래프와 무방향 그래프로 나눌 수 있는데, 더 자세한 내용은 추가로 포스팅하려고 한다.

그래프 탐색

그래프 탐색이란 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

이 글에서 설명하려는 DFS(Depth-First Search)는 그래프 탐색이다. 추후에 다룰 예정인 BFS(Breadth-First Search) 또한 마찬가지이다. 이외에도 다익스트라(Dijkstra), 플로이드 와샬(Floyd Washall)이 있다. 각 탐색 기법은 상황에 맞춰 적절한 것을 사용한다.

깊이 우선 탐색 DFS(Depth-First Search)

DFS 과정에 대해 자세히 설명하기 전, 이 이미지를 통해 간략히 알아보자. 노드 1을 시작으로 차례대로 노드 9까지 순회한다. 진행되는 방향을 보면 한 가지의 끝까지 탐색하고, 그 다음 가지를 순차적으로 탐색한다. 전체적 위에서 아래로 깊게 탐색이 진행되는 것을 볼 수 있다.

DFS란 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

예를 들면, 미로에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 길을 찾는 것이라고 할 수 있다. 깊이 우선 탐색은 전체 노드를 맹목적으로 탐색할 때 사용한다. 깊이 우선 탐색의 구현에서 중요한 것은 스택이다.

과정

위에서 사용한 트리형태의 그래프의 과정을 자세히 설명하고자 한다.

트리의 루트 노드인 노드 1을 기준으로 탐색을 시작한다. 스택 노드 1을 넣는다. 노드 1과 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.

아직 방문하지 않은 노드 2를 스택에 넣어준다. 다시 노드 2와 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.

노드 3을 스택에 넣어주고, 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.

그러나 노드 3과 연결된 노드는 노드 2뿐이며, 이미 방문했으므로 이번 분기의 탐색이 완료된 것이기 때문에 노드 3을 스택에서 빼낸다.

스택의 가장 위에 위치한 노드 2와 연결된 아직 방문하지 않은 노드가 있는지 확인한다. 그러나 존재하지 않기 때문에 노드 2를 스택에서 빼낸다.

앞의 과정을 계속 반복한다. 노드 1과 연결된 노드 중 방문하지 않은 노드 4를 스택에 추가하고, 노드 4와 연결된 노드 5를 다시 스택에 추가한다.

노드 5와 연결된 노드를 확인하고 방문하지 않은 노드 6을 스택에 추가한다.

노드 6와 연결된 노드를 확인한다. 방문하지 않은 노드가 없으므로 스택에서 제거한다. 노드 5도 마찬가지로 스택에서 제거한다. 노드 4와 연결된 또다른 노드를 확인한다.

노드 7을 스택에 추가한다. 연결된 노드 중 방문하지 않은 것이 없으므로 스택에서 제거하고, 노드 4 또한 모두 방문했으므로 스택에서 제거한다.

노드 1과 연결된 마지막 노드 8을 스택에 추가하고, 다음 노드를 탐색한다.

노드 9를 스택에 추가한다. 방문할 노드가 없으며, 노드 8 또한 마찬가지 이므로 스택에서 제거한다.

방문하지 않은 노드가 더이상 존재하지 않기 때문에 노드 1을 스택에서 제거해 탐색을 마친다.

👑 프로그래머스 문제에 적용해보자

프로그래머스의 DFS 문제의 풀이를 가볍게 해보려고 한다. 물론 문제에 대한 해결방법은 다양하니 그 중 하나로 여기길 바란다.

1) 여행경로

주어지는 tickets가 [["ICN","A"],["B","ICN"],["C","B"],["B","C"],["B","ICN"]] 이라면, 아래의 형태로 나타낼 수 있다.

이 문제는 ICN 노드를 루트 노드로 하여, 깊이 우선 탐색을 적용해 모든 티켓을 사용하는 방법을 찾아낼 수 있다. ICN 노드에서 A 노드를 먼저 방문하면 나머지 노드를 방문할 수 없으므로 답이 될 수 없다. 다음 분기에 B 노드를 먼저 방문하여 모든 티켓을 사용할 수 있으므로 ["ICN", "B", "C", "B", "ICN", "A"]가 답이 될 것이다.