파이썬 자료구조 - DFS와 BFS

자료를 탐색하는 알고리즘의 대표적인 방법은 2가지가 있다.

DFS(깊이 우선 탐색)와 BFS(넓이 우선 탐색)이다.

 

이런 그래프가 있을 때, 우리는 모든 알파벳을 탐색해보려고 한다.

DFS는 시작 정점에서 한 방향으로 깊이 탐색해 간다. 더 이상 갈 곳이 없게 되면 가장 마지막에 만난 갈림길로 돌아와서 다른 방향으로 탐색을 계속 반복한다.

 

이것을 그림으로 표현하면

이렇게 되는 것이다.

A에서 탐색을 시작하여 B로 간다. 여기서 더 깊게 들어갈 수 있는 E, F가 존재하므로 E로 들어간다. E에서는 더 깊게 내려갈 곳이 없으므로 마지막 갈림길인 B로 되돌아온다. 그리고 다시 F를 탐색하고 깊게 내려갈 곳이 없으니 B로 다시 돌아온다. B에서 더 내려갈 곳이 없으므로 마지막 갈림길은 A로 바뀌고, 다시 A로 올라가 C로 내려가게 되는 것이다.

 

따라서 이 알고리즘을 코드로 구현하려면 스택을 사용하는 것이 편리하며, 

# 방문한 지점 A를 넣고, stack에도 시작점인 A를 넣는다.
stack[A], visited[A]   

# 더이상 방문할 곳이 없을 때까지,(스택이 빌 때까지)
while stack:
	# 현재 지점을 뽑아서 current에 넣는다.
	current = stack.pop()  
    	# 만약 밑으로 으로 계속 탐색할 것이 있다면,
		for neighbor in direction[current]:  
       		# 그리고 그 항목들을 방문하지 않았다면,
			if not neighbor in visited:  
            	# 스택에 항목을 넣어주고 방문했다고 표시해준다.
				stack.append(neighbor)
				visited.append(neighbor)  

return

이렇게 구현할 수 있다. DFS를 통하면 위의 그림에서 탐색 결과는, 

A, B, E, F, C, D, G, H가 되는 것이다.

---

BFS는 탐색 시작점에서 인접한 곳들을 먼저 차례로 방문한 후에, 방문했던 곳을 시작점으로 다시 인접한 곳들을 방문하는 방식이다. 다시 말해, DFS는 밑으로 깊게 탐색한 것이라면, BFS는 옆으로 넓게 탐색한 것이라고 볼 수 있겠다.

 

이렇게 탐색하게 되는 것이다. A를 시작점으로 A에서 갈 수 있는 모든 점들을 방문하고,

다음으로 방문한 점에서 또 갈 수 있는 모든 점들을 방문한다. 다시 되돌아 오는 BFS와 다른 방식으로, 큐를 사용하는 것이 편리하다.

 

# 큐와 방문 지점 설정
queue = [A]
visited = []
while queue:
# 현재 방문한 위치를 pop
	current = queue.pop(0)
	for neighbor in direction[current]:
		if not neighbor in visited:
			queue.append(neighbor)
	visited.append(current)

return

이렇게 구현할 수 있다. 탐색 결과는,

A, B, C, D, E, F, G, H가 되는 것이다.

 

탐색 알고리즘의 기본은 미로 찾기 등에서 사용할 수 있다.

이에 여러 방법을 공부할 수록 좋을 것이다.