컴언

'너비 우선 탐색'에 해당되는 글 1건

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

[알고리즘] 너비 우선 탐색(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) >>> [['부산', '울산', '대구', '세종', '서울', '평양'], ['부산', '여수', '광주', '세종', '서울', '평양']]


참고 자료