깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

DFS의 용도

깊이 우선 탐색은 BFS와 마찬가지로 그래프를 방문하거나 탐색하는 방법 중 하나이다.

2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

 

DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수 (그래프의 최대 경로)가 정해져 있거나 예측 가능한 경우에 주로 사용한다.

 

DFS의 과정

1. 방문한 정점에서 해야 할 작업 진행
2. 현재 정점과 연결된 정점 중 아직 방문하지 않은 정점 방문
3. 만약 더 이상 방문할 정점이 없다면 이전 정점으로 되돌아간다
4. 1~3 반복
   

 

탐색 과정

BFS에서는 큐(Queue)를 사용했지만 DFS에서는 스택(Stack)을 사용한다.

스택을 사용하는 이유는 위에서 설명한 DFS의 과정 중 3단계에서 더 이상 방문할 정점이 없다면 이전 정점으로 되돌아가는 부분 때문이다.

하지만 스택을 직접 구현할 수도 있지만 주로 재귀적인 방법을 사용하는 것이 일반적이다.

 

1번부터 탐색을 시작한다.

1번과 연결된 정점 중 아직 방문하지 않은 2, 3, 4 정점 중에서 2번을 선택해 이동한다.

 

2번 정점과 연결 된 정점이 없으므로 다시 1번 정점으로 돌아간다.

 

1번 정점과 연결된 정점 중에 아직 방문하지 않은 3번 정점으로 이동한다.

 

3번 정점과 연결 된 정점 중 아직 방문하지 않은 정점인 4번 정점으로 이동한다.

 

4번 정점과 연결된 정점 중 아직 방문하지 않은 정점인 5번 정점으로 이동한다.

 

5번 정점과 연결된 정점이 없으므로 4번 정점으로 되돌아간다.

 

4번 정점과 연결된 정점이 없으므로 3번 정점으로 되돌아간다

 

3번 정점과 연결된 정점이 없으므로 1번 정점으로 되돌아간다

 

1번 정점과 연결된 정점이 없다.

모든 정점을 방문했으므로 탐색을 종료한다.

 

파이썬 구현

arr = [[], [2, 3, 4], [1], [4, 5], [3, 5], [3, 4]]
chk = [False] * 1010


def DFS(start):
    if chk[start]: return # 이미 방문한 정점이라면 방문을 종료
    chk[start] = True
    
    print(start)  # 방문 노드 출력
    
    for node in arr[start]:
        DFS(node)
        
DFS(1)

그래프를 표현하기 위해 arr에 중첩리스트를 사용했다. 내부의 리스트는 해당 인덱스(정점)과 연결된 정점을 뜻한다.

정점 방문 여부를 체크하기 위해 chk 리스트에 False를 많이 넣었다.

 

재귀를 사용하면 시스템 내부적으로 스택을 사용하며 return되면 스택에서 pop()을 하는 효과와 같다.

 

chk[]를 통해 이미 방문한 정점임을 확인했다면 return으로 빠져나오고,

방문하지 않았다면 True로 방문 처리를 한 후 작업을 진행한다.