DFS(깊이우선탐색) Python코드로 이해하기

DFS(깊이우선탐색)

dfs는 이름에서부터 알 수 있듯이 깊이를 우선으로 하여 탐색하는 알고리즘.

dfs를 구현하고자 할 때는 스택 자료구조 혹은 재귀 함수를 이용.

 

1. 먼저 탐색을 시작할 노드를 스텍에 넣고 방문 처리.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있다면 그 노드 또한 스택에 넣고 방문 처리. 
   혹은 만약 스택에 최상단 노드에 방문하지 않은 인접 노드가 없으면 그냥 스택에서 해당 노드를 꺼내면 된다.
3. 이러한 과정을 더 이상 수행할 수 없을 때까지 반복. 

 

어떤 노드부터 방문할지를 결정하기 위한 기준은 문제에서 요구하는 내용에 따라서 달라질 수 있고 어떤 노드부터 방문하더라도 상관이 없는 경우도 있다.
흔히 번호가 낮은 로드부터 방문한다고 가정하고 설명을 진행하는 경우가 많다.

 

파이썬에서는 이와 같이 그래프를 표현하기 위해 이차원 리스트 형태를 사용할 수 있다. 
일반적으로 그래프 문제가 출제되면 노드의 번호가 1번부터 시작하는 경우가 많다.

따라서  인덱스 0에 대한 내용은 비우고 1번 인덱스부터 해당 노드에 인접한 노드가 무엇인지 리스트 형에 담아주자.

그래서 1번 노드와 연결되어 있는 건 2번 3번 8번이라고 리스트를 초기화한 것을 확인할 수 있고, 
마찬가지로 2번 노드와 연결된 건 1번 노드인 7번 노드 이렇게 들어가는 걸 확인할 수 있다. 

방문 처리를 위해서 마찬가지로 하나의 1차원 리스트를 만들어주자.

단 여기에서 기본적으로 모든 값들은 False 값으로 초기화하여 아직 하나도 방문하지 않은 것처럼 처리하자. 
여기서도 0번째 인덱스를 사용하지 않게 하기 위해 1 더 큰 리스트를 생성하자.

그 노드를 방문했다는 의미로 해당 노드의 번호를 출력할 수 있도록 하고

이어서 현재 확인하고 있는, 즉 스택의 최상단에 있는 원소와 연결된 다른 노드를 하나씩 확인하면서

만약에 그 노드가 즉 인접한 노드가 방문되지 않은 상태라면 그 노드에 대해서도 재기 함수를 이용해 방문을 진행할 수 있다. 
이처럼 재귀적으로 방문하지 않은 노드들을 계속해서 방문한다는 점에서 최대한 깊게 그래프를 탐색할 수 있는 것.