알고리즘 - 깊이 우선 탐색

탐색

탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다.
주어진 데이터의 성질(정렬 혹은 비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다.

깊이 우선 탐색(DFS)

DFS(depth-first search)는 그래프 완전 탐색 기법 중 하나로 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
그래프 완전 탐색	- 재귀함수로 구현 - 스택 자료구조 이용	O(V+E)

재귀함수로 구현 시 스택 오버플로(stack overflow)에 유의해서 구현해야 한다. 하지만 스택보다는 스택의 성질을 가진 재귀 함수로 많이 구현하는 편이다.
응용해서 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

핵심 이론

DFS는 한번 방문한 노드를 다시 방문하면 안되서 노드 방문 여부를 체크할 배열이 필요하다.
그래프는 인접 리스트로 표현하고 탐색 방식은 후입선출 특성을 가지므로 스택을 사용해서 알아보자.

DFS를 위해 필요한 초기 작업

• 인접 리스트로 그래프 표현하기
• 방문 배열 초기화하기
• 시작 노드 스택에 삽입하기

1. DFS를 사용할 노드를 정한 후 사용할 자료구조 초기화하기

스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F 가 된다.

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다.
방문 배열은 T,T,T,F,F,F 가 된다.

3. 스택 자료구조에 값이 없을 때까지 반복하기
   앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다. 이때 이미 다녀간 노드는 방문배열을 바탕으로 재삽입하지 않는 것이 핵심이다.

list[0] = [2,3];
list[1] = [5,6];
list[2] = [4];
list[3] = [6];
list[4]
list[5]

스택에서 3을 꺼내며 탐색 순서에 기록하고 인접 노드 4를 스택에 삽입하고 방문 배열에 체크한다.
스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.