[ Python ] BFS 너비 우선 탐색과 DFS 깊이 우선 탐색 ( 1 )

우리가 매우 쉬운 미로를 풀 땐 손을 가져다 대지 않고, 특별한 알고리즘 없이 대충 보는것만으로도 직관적으로 길이 보일 때가 있다. 그걸 따라서 코딩을 하자니 그 간단한 미로조차도 풀기 위해선 알고리즘이 필요한데 내가 어떻게 출구를 찾았는지 코드화 하자니 막막하다. 당신이 수학적 사고가 뛰어나서 바로 생각이 났다면, 나와는 다르게 정형화 된 알고리즘이 필요 없겠지만. 무언가를 창조 해 내려면 모방에서부터 시작한다고 하지 않는가? 그런 알고리즘의 기초와 같은 알고리즘을 오늘 소개하고자 한다.

BFS ( Breadth First Search ) 너비 우선 탐색과 DFS ( Depth First Search ) 깊이 우선 탐색이다. 흔히 이런 철자가 비슷한 약자들은 헷갈리기 마련인데, 두 알고리즘은 서로 상당히 달라서 단어만 알면 헷갈릴 일이 딱히 없다.

첫번째 DFS 깊이 우선 탐색은 한개의 노드를 선택해서 더이상 뻗어나갈 수 없을때까지 뻗어나갔다가, 더이상 뻗어나갈 수 없다면 그 상위 노드로 이동해서 다른 노드를 끝까지 뻗어나가는것을 반복하는 방식이다.
두번째 BFS 너비 우선탐색은 시작 노드에서 접하는 모든 노드를 순회하고 저장했다가, 저장된 노드에서 다시 접하는 모든 노드를 순회하고 저장하는것을 반복하는 방식이다.

그 중에서 오늘은 깊이 우선탐색 DFS 를 우선 살펴보고자 한다.

visited = [False]*node

def DFS(data,node,visited):
	#현재 노드 방문처리
    visited[node] = True
    
    #현재 노드에 연결된 다른 노드 재귀적 방문
   	for i in data[node]:
    
	    if not visited[i]:
        	DFS(data,i,visited)

DFS(data,1,visited)

DFS에서 상당히 중요한 부분은, 방문처리를 해주어야 한다는 것이다. 만약 각각의 노드가 한개의 노드에만 연결이 되어있다면, 상관이 없겠지만 만약 두개 이상의 노드와 연결이 되어있다면, 그리고 이런 트리 모양의 노드가 아니라 불규칙한 모양의 노드라면 루프가 발생할 수 있기 때문이다. 단순히 모든 노드를 방문처리해야하기에, visited 리스트를 생성했지만 만약 거리가 주어진다면, 초기 데이터를 무한 (1e9) 으로 설정한 후 방문할 경우 min() 함수를 이용하여 해당 노드까지의 거리를 초기화해주는 방법을 사용하기도 한다.

앞선 글에서 소개했던 Stack 자료구조를 이해하고있다면 더욱 쉽게 이해할 수 있다. 대략적인 플로우차트는 다음과 같다

1번 노드에서 시작 → 2번 노드 Push / 2번 노드와 인접한 3번노드로 이동 → 3번노드 Push / 3번 노드에는 인접노드가 없으므로 다시 3번 노드 Pop → 2번노드에서 인접한 노드중 방문하지 않는 노드가 없으므로 2번노드 Pop → 1번노드에 인접 노드 중 4번 노드가 방문하지 않았으니 4번노드로 이동 → 4번노드Push / 4번노드와 인접하고 방문하지 않은 5번노드로 이동...

DFS 의 장점은 BFS와는 다르게 현재 방문하고있는 경로상의 노드만을 Stack 에 담으면 되기때문에, 저장공간을 비교적 적게 사용한다는 점이다.

[[ 마무리 ]]
Python 에서는 Stack 자료구조를 따로 제공하지 않으므로, 그냥 리스트 자료구조를 사용하는것과 시간, 저장공간적 차이가 크지 않다. 하지만 그럼에도 해당 알고리즘을 소개하는것은 구현의 간단함과 단순히 가장 멀리있는 자료를 찾아야할 때도 있고, 상황에 따라서 BFS보다 더 좋은 해결책이 되기도 하기 때문이다. 바로 이어지는 글에서는 오늘 다루지 않은 BFS 에 대해서 다루고자 한다.