이코테 2021, DFS 개념 정리 (파이썬)

DFS

- 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

- 스택 자료구조(혹은 재귀 함수)를 이용한다.

 

 

DFS의 동작과정

0. 그래프를 준비한다. (해당 강의에서는 번호가 낮은 인접 노드 순으로 방문하는 기준을 세움)

 

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

 

시작 노드인 1을 스택에 삽입하고 방문 처리한다.

 

 

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없드면 스택에서 최상단 노드를 꺼낸다.

 

1을 기준으로 2, 3, 8의 노드가 있는데, 방문 기준에 따라 2를 먼저 스택에 삽입한 뒤 방문처리한다.

 

3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

2에게 인접한 노드가 1, 7이 있지만 방문하지 않은 7을 스택에 삽입하고 방문처리한다.

 

마찬가지로 7에서 인접한 2와 6, 8 노드 중 방문하지 않고 작은 노드인 6을 삽입하고 방문처리 한다.

 

6번 노드에겐 방문하지 않은 인접 노드가 없기에 6번 노드를 꺼낸다.

 

7번 노드에서 방문하지 않은 8번 노드를 스택에 삽입하고 방문처리한다.

 

이를 반복처리할 때 1 -> 2-> 7 -> 6 -> 8 -> 3 -> 4 -> 5 순서로 방문하게 된다.

 

 

코드

- 위의 그래프를 다음과 같이 코드로 작성할 수 있다.

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * len(graph)

def dfs(graph, v, visited):
	# 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문하여 스택에 쌓는 듯이 동작하도록 한다.
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

print('dfs로 호출한 결과 :', end='')
dfs(graph, 1, visited)

 

- 위에서 볼 수 있듯이 인접해있는 노드를 타고 들어가 가장 깊숙히 있는 노드를 우선적으로 스택에 삽입하고 방문 처리하는 알고리즘을 DFS라고 한다. 

- 처음 접해보는 개념이기에 매우 어렵고 생소한 개념이었지만 동빈나님의 유튜브 강의에서 매우 잘 설명이 되어있어 이해하는 데 많은 도움이 됐다.

- 관련 문제를 푸는 데 꽤나 오랜 시간이 걸렸다. 하루에 한 두개씩 꾸준히 푸는 연습이 필요할 것 같다.

 

 

 

강의 자료 출처 : 동빈나 이코테 2021 강의 몰아보기 DFS 알고리즘 영상