깊이 우선 탐색 (DFS)

동빈나 실전 알고리즘 강좌 - 17강 DFS

깊이 우선 탐색 (DFS) 알고리즘 개념

깊이 우선 탐색(Depth First Search, DFS)은 탐색을 할 때 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다.

• 너비 우선 탐색(Breadth First Search, BFS) 에서는 큐(Queue)의 자료 구조가 사용되었다.

여기서, 깊이 우선 탐색(Depth First Search, DFS)는 스택(Stack)의 자료 구조를 사용하여 구현한다.

Tip! 💡
사실 스택을 사용하지 않아도 구현이 가능하다는 특징이 있다.
그 이유는 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다.

DFS는 맨 처음에 시작 노드(Start Node)를 스택에 삽입하면서 시작한다.
또한, 시작 노드를 방문 한 점을 기억해야한다. (방문 처리는 빨간색으로 색칠)

이제, DFS는 다음과 같은 간단한 알고리즘에 따라 작동한다.

1. 스택의 최상단 노드를 꺼낸다.
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리를 하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

위 1번과 2번을 계속해서 반복한다.

쭉 방문하게 되면 아래의 그림과 같이 모두 다 방문하게 된다.

이제부터는 남은 노드들을 모두 스택에서 꺼내주기만 하면 된다.

따라서, 방문 경로는 1→2→3→6→7→4→5 이다.

깊이 우선 탐색 (DFS) 알고리즘 코드

해당 개념을 python 코드로 작성해보자❗

동빈나 실전 알고리즘 강좌에서는 C++로 되어있기에 python으로 변경하여 코드를 작성하였습니다.

number = 7
check = [False for _ in range(number + 1)] # 방문을 저장할 리스트
arr = [[] for _ in range(number + 1)] # 원소 리스트 [=> 1부터 시작할 수 있도록 8로 만들기]

def dfs(x): # 재귀 함수로 접근
    if check[x]: return;
    check[x] = True

    print(x, end=' ')
    for i in range(len(arr[x])):
        dfs(arr[x][i])

# 1과 2를 연결 한다.
arr[1].append(2)
arr[2].append(1)

# 1과 3을 연결한다.
arr[1].append(3)
arr[3].append(1)

# 2과 3을 연결한다.
arr[2].append(3)
arr[3].append(2)

# 2과 4을 연결 한다.
arr[2].append(4)
arr[4].append(2)

# 2과 5를 연결한다.
arr[2].append(5)
arr[5].append(2)

# 3과 6을 연결한다.
arr[3].append(6)
arr[6].append(3)

# 3과 7을 연결한다.
arr[3].append(7)
arr[7].append(3)

# 4와 5를 연결한다.
arr[4].append(5)
arr[5].append(4)

# 6과 7을 연결한다.
arr[6].append(7)
arr[7].append(6)

# DFS를 수행한다.
dfs(1)

이러한 DFS는 깊이를 우선으로 하여 탐색한다는 특성이 중요한 것이며, 이를 이용해 다른 알고리즘에 적용한다는 것이 핵심이다.
또한, 스택을 직접 사용하지 않고 재귀 함수를 이용해 간략하게 함수를 구현한 것을 알 수 있다. (프로그래밍 대회에서 많이 사용)

[References]
https://blog.naver.com/ndb796/221230945092
https://youtu.be/l0Rsu7dziws?si=ver-7g5BAmfH5tQr