컴언

[알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법

자료구조

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


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


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


 

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


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


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


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


기본 원리

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





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


산이 2000m 라고 할 때, BFS는 2000m -> 1900m 훑고 -> 1800m 훑고 -> ... -> 100m ~ 0m 까지 훑어서 탐색하는 것이죠. 좀 더 정의에 관련해서 설명하자면, 시작점 (2000m) 에서 같은 거리에 있는 원소들을 다 훑어야만 그 거리보다 더 먼 곳 (1900m~0m) 으로 차례차례 진격할 수 있는 것입니다.



가족 관계를 예로 들어 설명해보겠습니다. 자 오늘은 추석입니다~ 우리 민족의 대명절 추석에 아차! 일이 생겨 가족 모임에 가지 못하게 됐습니다. 저는 가족 관계를 원만하게 하는 것을 미덕으로 생각하는 사람이라서 8촌 이내의 모든 가족에게 빠짐 없이 연락하고 싶습니다. BFS 의 방식으로 연락을 한다면 어떻게 되는걸까요? 먼저 1촌인 부모님과 자녀에게 연락을 합니다. 그다음에 2촌인 가족들에게 연락을 돌리고요, 계속해서 3, 4, ... 8촌 까지 연락을 하면 모든 가족에게 빠짐없이 연락한 것이 됩니다. 이러한 순서로 그래프를 탐색하는 것이 BFS 입니다.



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



BFS의 방문 순서

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


맨 위를 첫 번째 단(Tier 1)이라고 하고 그 뒤로 두 번째 단, ... 이어진다고 합시다. 먼저 첫번째 단의 원소인 1 을 찍고 갑니다 (방문visit합니다). 그 다음 두번째 단에는 원소들을 전부 찍고, 세번째 단도 전부 찍고,... 단(Tier) 별로 방문하는 것을 볼 수 있습니다. 각 노드 안의 숫자는 방문 순서를 나타냅니다.



파이썬으로 구현하기

이제 BFS 를 실제 코드로 구현해보도록 합시다. BFS 에서 중요한 요소는 바로 큐 (Queue) 자료 구조입니다. 


좀 흥미로운 그래프를 가져왔습니다. 우리나라 정부 청사들이 다 세종시로 옮겨가는 중인데요, 세종시에서 BFS 를 통해 우리나라의 주요 장소를 (평양까지...!!ㅋㅋㅋ) 순회해보겠습니다.


순회 과정을 아래에 차근 차근 표현해 놓았으니, 아래 그래프를 새 창에 열어놓고 과정을 천천히 따라가보세요.



1. 먼저 Queue 에 시작점인 세종시를 넣습니다. 


그 다음, 큐의 맨 앞에 있는 세종을 불러서Queue.dequeue() 방문visit합니다. 세종시에 이어진 서울, 강릉, 대구, 광주을 큐에 줄세웁니다Queue.enqueue(세종의 자손 노드들) . 


>> 큐의 뒤

IN 

(enqueue)

  

 광주

대구

강릉

울 

세종 (Visit)

 >> 큐의 앞

OUT

(dequeue)

방문한 곳: {세종, }


2. 큐의 맨 앞에 있는 서울을 큐에서 내보내고 방문합니다. 서울시에 이어진 평양, 인천을 큐에 줄세웁니다Queue.enqueue(서울의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN 

 

 

인천 

 

광주

대구

강릉

서울 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, }


3. 큐의 맨 앞에 있는 강릉을 큐에서 내보내고 방문합니다. 강릉시에 이어진 독도를 큐에 줄세웁니다Queue.enqueue(강릉의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN 

 

독도 

 인천

평양

광주

대구

강릉 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, }


4. 큐의 맨 앞에 있는 대구를 큐에서 내보내고 방문합니다. 대구시에 이어진 울산을 큐에 줄세웁니다Queue.enqueue(대구의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

 

 울산

독도 

 인천

평양

광주

대구 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, }


5. 큐의 맨 앞에 있는 광주를 큐에서 내보내고 방문합니다. 광주시에 이어진 여수를 큐에 줄세웁니다Queue.enqueue(광주의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

 

여수

 울산

독도 

 인천

평양

광주 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, }


6. 큐의 맨 앞에 있는 평양을 큐에서 내보내고 방문합니다. 평양시에 이어진 서울은 이미 방문했네요. Queue.dequeue()  하고 평양 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

 

 

 여수

 울산

독도 

 인천

평양 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, }


7. 큐의 맨 앞에 있는 인천을 큐에서 내보내고 방문합니다. 인천시에 이어진 서울은 이미 방문했네요. Queue.dequeue()  하고 인천 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

  

 

 여수

 울산

독도 

인천 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, }


8. 큐의 맨 앞에 있는 독도을 불러서 방문합니다. 독도에 이어진 강릉은 이미 방문했네요. Queue.dequeue()  하고 독도 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

   

 

 여수

 울산

독도 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, }



9. 큐의 맨 앞에 있는 울산을 큐에서 내보내고 방문합니다. 울산시에 이어진 부산을 큐에 줄세웁니다Queue.enqueue(울산의 자손 노드들) . 단, 대구는 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

    

 부산

 여수

울산 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, }


9. 큐의 맨 앞에 있는 여수를 큐에서 내보내고 방문합니다. 여수시에 이어진 부산을 큐에 줄세웁니다Queue.enqueue(여수의 자손 노드들) . 단, 광주는 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

    

 부산

 부산

여수 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, }


10. 큐의 맨 앞에 있는 부산을 큐에서 내보내고 방문합니다. 부산시에 이어진 여수, 울산은 모두 이미 방문했으므로 부산 visit 만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

    


 부산

부산 (Visit)

 >> 큐의 앞

나가는 방향

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, 부산, }



11. 마지막으로 큐에 남아있는 부산은 이미 방문되어 있으므로 큐에서 내보냅니다. 그 뒤에 큐에 남은 장소가 없으므로 BFS 탐색이 끝났습니다.


>> 큐의 뒤

IN  

    


 

부산 (이미 방문)

 >> 큐의 앞

나가는 방향

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, 부산, }


결과를 보니깐 11개 장소를 빠짐 없이 방문한 것을 볼 수 있습니다. 오예!


 

이 긴 과정을 파이썬 코드로 나타내보겠습니다. 


그래프는 파이썬에서 다음과 같이 나타낼 수 있겠습니다.

 
korea = {'세종': set(['서울', '강릉', '대구', '광주']),
         '서울': set(['평양', '인천', '세종']),
         '강릉': set(['독도', '세종']),
         '광주': set(['세종', '여수']),
         '대구': set(['세종', '울산']),
         '평양': set(['서울', ]),
         '인천': set(['서울', ]),
         '독도': set(['강릉', ]),
         '여수': set(['광주', '부산']),
         '울산': set(['대구', '부산']),
         '부산': set(['여수', '울산']),
         }


아래가 bfs 함수입니다.

 
def bfs(graph, root):
	visited = [] # 방문한 곳을 기록
	queue = [root] # 큐에 시작점을 줄세움

	while queue: # queue 가 빌 때 까지 탐색을 계속
		vertex = queue.pop(0) # 큐의 맨 앞의 원소를 방문할 꼭짓점으로 설정

		if vertex not in visited: # 꼭짓점이 방문된 적이 없다면 방문 기록에 추가
			visited.append(vertex)
			for node in graph[vertex]: # 꼭짓점에 연결된 노드들 중 
				if node not in visited: # 방문 안 된 곳 만을
					queue.append(node) # 큐에 줄세움

	return visited

##### 실행결과 #####
print(bfs(korea, '세종'))
>>> ['세종', '서울', '대구', '강릉', '광주', '인천', '평양', '울산', '독도', '여수', '부산']




BFS 경로탐색


방문 순서를 기록하면서 재귀 호출을 이용하면 아래와 같이 부산에서 평양까지의 경로 탐색도 할 수 있습니다. 


paths = [] def bfs_paths(graph, start, end, path=[]): # 그전 방문했던 노드들 유지. 이번 차례 방문하는 꼭짓점도 visited에 추가 path = path + [start] # 목적지에 도달했으면 paths 에 경로 기록 후 종료 if start == end: paths.append(path) # bfs 와 같음 queue = [start] while queue: vertex = queue.pop(0) for node in graph[vertex]: if node not in path: # 방문하지 않은 자손들에 대해 쭈우욱 재귀 호출 BFS_paths(graph, node, end, path) ##### 실행결과 ##### bfs_paths(korea, '부산', '평양') print(paths) >>> [['부산', '울산', '대구', '세종', '서울', '평양'], ['부산', '여수', '광주', '세종', '서울', '평양']]


참고 자료


[알고리즘] 깊이 우선 탐색(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