2021.3.7 TIL : [알고리즘] 깊이 우선 탐색(Depth First Search)

<깊이 우선 탐색>

깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. 깊이 우선 탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용한다. 깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조에 기초한다. 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있다.

 

dfs의 순서 :

   1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

   2. 스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

   3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

깊이 우선 탐색 알고리즘은 스택(stack) 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 O(N)의 시간이 소요된다. 

 

깊이 우선 탐색은 재귀 함수를 이용해서 구현하는 방법과 스택을 이용해서 하는 방법으로 총 두 가지가 있다. 두 가지를 모두 의사코드로 표현해보면 다음과 같다.

<재귀 함수>

curr_time = 1 #전역 변수. 방문할 때마다 1씩 증가시킴

DFS(v) #현재 노드 v를 방문 중이라는 함수를 의미
	mark[v] = 'visited'
	pre[v] = curr_time #v의 첫 번째 방문 시간
	curr_time += 1
	for each edge(v, w): #w는 v에 인접한 노드
		if mark(w) != 'visited':
			parent[w] = v #parent에는 w를 방문하기 직전 노드를 기록
			DFS(W)
	#for loop을 통해 v에 인접한 모든 노드를 고려함
	post[v] = curr_time #v에 인접한 모든 노드를 방문해서 방문할 노드가 없는, dfs가 완료된 시간을 기록(이제 back-track 해야 함)

---

<스택>

DFS(s) #s는 시작 노드
	stack.push((∅, s)) #튜플 자료형으로 stack에 추가. 부모노드와 현재 방문노드를 튜플로 넣어주어도 되고, 현재 방문 노드만 넣어 기록할 수도 있다)
	while stack: #while stack is not empty 와 같은 뜻
    	p, v = stack.pop() #p는 부모 노드, v는 현재 방문하는 노드
        if v is unmarked: #mark[v] != 'visited'
			mark[v] = 'visited'
			parent[v] = p
			for each edge(v, w):
				if w is unmarked:
					stack.push((v, w))

만약 하나의 그래프 안에서 모든 노드가 사이클로 이루어지지 않은 경우, (즉 두 개의 별도 그래프로 나눌 수 있는 경우) 이를 DFS Tree라고 하며 다음 그림과 같은 구조를 의미한다.

이런 구조는 다음과 같은 코드를 추가해주면 노드를 빠뜨리지 않고 방문할 수 있다.

DFSAll(G) : #그래프 G를 DFS Search
	for all nodes in G:
    	mark[v] = 'unvisited'
        for all nodes v:
        	if mark[v] != 'visited'
            	DFS(v)

이와 관련된 알고리즘 문제에 프로그래머스>네트워크 문제가 있다. 나는 개인적으로 이 개념을 적용해 푸는 것이 어려워서.. 개념 강의만 네번 돌려 듣고, 문제도 강의 들으면서 3일은 붙잡고 있었다. 곧 풀이도 업데이트할 예정이니, 풀이와 함께 확인해 보면 좋을 것 같다.