컴언

'깊이 우선 탐색'에 해당되는 글 1건

  1. [알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법 (3)

[알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법

자료구조

이 글에서는 트리나 그래프를 순회(traverse)/탐색(search)하는 알고리즘 중에 하나인 깊이 우선 탐색 (Depth First Search, DFS) 에 대해 다룹니다.  너비 우선 탐색에 대해서는 아래 글을 참고해주세요  


2016/07/05 - [자료구조] - [알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법



그래프 탐색의 필요성이미 BFS 에 대한 제 글을 읽으셨다면 그래프 탐색의 필요성을 넘어가시면 됩니다. ^ㅍ^


 

사진 출처: http://pages.cs.wisc.edu/~paton/readings/Graphs/


그래프 자료구조라고 하면 어떤 것이 생각나시나요? 위와 같이 아기자기한 그림인가요? 


하지만 아래를 보면 어떠신가요?

사진 출처: 오마이뉴스


자료 구조 설명하다가 무슨 삼성 그룹의 순환 출자에 대한 그림을 가져왔냐고 화를 내실지도 모르겠습니다만 꼭짓점(vertex)이 수없이 많은 그래프라고 생각해보세요. 이 모든 꼭짓점을 빠짐없이 방문하려면 어떻게 해야할까요? 선형구조인 단순한 리스트(List) 였다면 리스트의 총 원소 개수 N을 구해서 0~ N 까지 위치의 원소를 출력하면 탐색 완료지만, 그래프에서는 노드에 순서대로 번호가 있는 것도 아니고 하기 때문에 모든 원소에 대한 탐색이 어려운 것입니다. 이 난관을 극복하기위해 DFS 같은 알고리즘이 필요한 것이죠.



기본 원리

아래 두 사진 출처: CS188: Artificial Intelligence, UC Berkeley (강의 슬라이드)

깊이 우선 탐색



너비 우선 탐색



위에 그림처럼 산과 그 속에 묻힌 보석을 찾아야하는 로봇이 있습니다. 로봇은 보석을 찾기 위해 첫번째 그림처럼 한없이 밑으로 내려가볼 수도 있고, 두번째 그림처럼 정상부터 점점 내려오면서 높이 별로 찾아볼 수도 있을겁니다. 전자와 같은 방식을 오늘 설명할 깊이 우선 탐색이라고 하고요, 후자는 너비 우선 탐색 (Breadth First Search, BFS) 라고 합니다. 둘은 산 속에 숨겨진 보석을 찾는다는 목표는 같지만, 그 찾는 순서가 다릅니다.


오늘 설명할 DFS 는 한 번 판곳은 땅바닥이 나올 때까지 죽도록 팝니다. 식물 뿌리를 생각해볼까요? 


이 식물의 뿌리는 네 방향으로 나뉘어집니다. 제가 각각 1, 2, 3, 4로 표시 했습니다.

이제 로봇이 1로 탐색하려고 들어갔다고 한다면... DFS 에 따르면 1의 줄기인 a, b, c 를 모두 다 찍고 가야합니다. 

마찬가지로 그 다음에 2에 들어갔다면 2에 연결 된 줄기 모두를 찍어야 3이나 4로 넘어갈 수 있는 거지요.



마침 엉덩국 씨의 유명한 짤이 생각나서 넣어봤습니다.


 한 곳을 팠을 때는 마음대로였겠지만, 나갈때는 아니란다! DFS 는 팠으면 끝까지 파고 난 다음에야 나갈 수 있는 것입니다.


귀여운 그림을 사용해서 설명을 해봤는데 실제 그래프를 통해 DFS 가 어떻게 이루어지는지 아래에서 살펴봅시다.


DFS의 방문 순서

1. 맨 위 root node (1) 에서 탐색이 시작한다고 가정.
2. 좌우 노드 중 왼쪽 노드를 항상 우선 탐색한다고 가정.
사진 출처: http://docs.seqan.de/seqan/1.2/streePreorder.png



위 그림에서 각 꼭짓점 안의 숫자는 방문 순서를 의미합니다. 맨 위 뿌리 노드에서 시작합니다. 가정에 따라 맨 왼쪽으로 가네요... 그리고 한없이 밑으로 갑니다. 왼쪽 3으로 갔다가 4로 가서 5, 6까지 내려갑니다. 다음, 현재 방문하지 않은 꼭짓점 중 가장 왼쪽이면서 위쪽에 있는 노드인 7로 갑니다. 그 뒤로는 위 그림의 방문 순서를 스스로 따라가보시기를 권합니다. 


파이썬으로 구현하기

제가 요즘 열심히 공부하는 Python 으로 DFS 를 구현해보고자 합니다. 중요한 점: DFS 를 구현할 때는 스택을 이용하는데, 그 이유를 아래 그림과 함께 보시죠.

사진 출처: https://en.wikipedia.org/wiki/Depth-first_search

 순서

(방문하고 있는)

꼭짓점

자손

 스택 

(빨간색 = 스택의 맨 위)

 1

 

 

   A

 2

 A (시작점)

 B, C, E

  B, C, E

 3

 B

 D, F

  D, F, C, E 

 4

 D

 없음

  F, C, E 

 5

 F

 E

  E, C, E 

 6

 E

 A (이미 방문)

   C, E 

 7

 C

 G

   G, E 

 8

 G 없음

  E (이미 방문)

 9

 스택이 비면 탐색 종료






1. 스택에 처음 시작점을 넣습니다stack.push(A).

2. 스택의 맨 위 원소를 빼낸stack.pop() (A) 가 현재 방문하고 있는 꼭짓점이 됩니다. 그 꼭짓점의 자손들 (B, C, E) 를 스택에 밀어 넣습니다stack.push(B, C, E).

3. 또 다시 stack.pop() (B) 를 방문합니다. 그 다음 B의 자손들 (D, F) 를 스택에 밀어 넣습니다stack.push(D, F).

4. stack.pop() (D) 를 방문합니다. D 의 자손은 없으니 다음 순서로 넘어갑니다.

5. stack.pop() (F) 를 방문합니다. F 의 자손(E) 를 스택에 밀어 넣습니다stack.push(E).

6. stack.pop() (E) 를 방문합니다. E 의 자손(A) 를 스택에 밀어 넣으려고 보니 이미 방문한 점이네요. 넣지 않고 다음 순서로 넘어갑니다.

7. stack.pop() (G) 를 방문합니다. G 의 자손은 없으니 다음 순서로 넘어갑니다.

8. stack.pop() 하니깐 이미 방문한 E가 나오네요. 다음 순서로 넘어갑니다.

9. 더이상 stack 에 남아있는 꼭짓점이 없습니다. 탐색을 종료합니다.



pseudo-code 로 DFS 과정을 대략 짜보겠습니다.

 
function DFS(Graph graph, Node root)
	Stack stack // Stack 선언

	stack.push(root)

	while 스택에 원소가 있을 동안 do
		방문할 꼭짓점 V = stack.pop() // 스택 맨 위의 원소를 꺼내서
		V.visit() // 방문
		stack.push(V 의 자손 노드들 *단, 이미 방문한 노드는 제외) // 방문한 노드의 자손 노드들을 스택에 push.
	end


자 이제 파이썬으로 코딩하기 전에, Graph 를 표현해야겠죠.


파이썬에서 Graph 는 아래 같이 원소와 연결된 원소들의 set 을 대응시킨 dictionary 자료형으로 표현할 수 있습니다. (Python Patterns - Implementing Graphs | Python.org)

#파이썬에서 위 그래프 표현
graph = {'A': set(['B', 'C', 'E']),
         'B': set(['A', 'D', 'F']),
         'C': set(['A', 'G']),
         'D': set(['B']),
         'E': set(['A', 'F']),
         'F': set(['B', 'E']),
         'G': set(['G'])}


자 그러면 DFS 를 구현해봅시다. 

def dfs(graph, root):
	visited = [] # 각 꼭짓점(vertex)이 방문되었는지 기록
	stack = [root, ] 

	while stack: # stack 이 비게 되면 탐색 끝
		vertex = stack.pop() # 방문되어지고 있는 꼭짓점
		if vertex not in visited: # 
			visited.add(vertex)
			stack.extend(graph[vertex] - visited)

	return visited;

########### 실행 결과 ###########
print(dfs(graph, 'A'))
>>> {'F', 'B', 'A', 'E'}

참고로 DFS 는 그래프에서 모든 꼭짓점을 찾아가는 과정이라고 생각하세요. dfs(graph, 'A') 의 결과가 저와 순서가 다른 것은 당연합니다. visited 는 순서가 없는 list 자료형이니까요. 중요한 것은 dfs 를 통해 모든 꼭짓점을 찾았느냐입니다.


이 DFS 를 재귀적으로(recursive) 구현도 합니다. 좀 더 깔끔해 보이는 장점이 있는데, 아래 코드를 함께 보시죠.

def dfs_recursive(graph, root, visited=None):
	if visited is None:
		visited = set()

	visited.add(root)

	# 주어진 root 과 연결되어 있는 다른 node 들에 대해 방문하지 않은 것들만 재귀 호출합니다.
	for node in graph[root] - visited:
			dfs_recursive(graph, node, visited)

	return visited



DFS 경로 탐색


그렇다면 DFS 로 A 부터 F 까지 가는 경로를 탐색해볼까요? 앞의 dfs 함수와는 달리 방문 순서를 순서대로 기록할 필요가 있다는 것만 기억하시면 되겠습니다.

 

paths = []

def dfs_paths(graph, start, end, visited=[]):
	# 그전 방문했던 노드들 유지. 이번 차례 방문하는 꼭짓점도 visited에 추가
	visited = visited + [start]

	# 도착했으면 paths 에 경로 기록하고 종료
	if start == end:
		paths.append(visited)

	# 현재 점의 자손 노드 중에 방문하지 않은 노드에 대해 재귀 호출
	for node in graph[start]:
		if node not in visited:
			dfs_paths(graph, node, end, visited)


########### 실행 결과 ###########
dfs_paths(graph, 'A', 'F')
print(paths)
>>> [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]



다음에는 너비 우선 탐색에 대해 다뤄보도록 하겠습니다.



참고 자료

http://pages.cs.wisc.edu/~paton/readings/Graphs/

Depth-First Search and Breadth-First Search in Python - Edd Mann