깊이 우선 탐색(Depth-First Search)

깊이 우선 탐색(DFS) 란 그래프를 탐색하는 방법 중 하나이다.

 

그림 1

그림 1을 예시로 들어보자.

DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법인데

탐색을 시작할 정점을 A라고 정해보자.

 

A에서 시작했을 때, A와 연결되어 있는 정점은 B, C이다.

이때 DFS는 자신과 연결되어 있는 정점을 먼저 탐색한다.

 일단 B부터 탐색해 보겠다.

 

그림 2

여기서 초록색은 이미 탐색한 정점, 파란색은 현재 도달한 정점이다.

여기서 B는 D와 E 를 갈 수 있다. A 도 갈 수 있지만 이미 탐색을 했기 때문에 D 와 E 중 하나를 탐색해 준다.

그림 3

이번엔 D에서 탐색할 수 있는 정점을 보면 H밖에 없다. 그러므로 H를 탐색해 준다.

 

그림 4

H에 도달했을 때, H에서 갈 수 있는 정점은 E다. 만약 이 그래프에 방향이 있다면, 방향에 따라 H에서 E로 갈 수 없을지도 모르지만, 현재 방향이 존재하지 않기 때문에 E를 탐색할 수 있다.

그러므로 E를 탐색해 준다.

 

그림 5

E에 도달했을 때, E는 더 이상 탐색할 정점이 없다. 이미 앞에서 먼저 탐색했기 때문이다.

그러면 이대로 탐색을 종료할 것인가?

아니다. 아직 C, F, G를 탐색하지 않았다. 그러면 어떻게 해야 될까?

그래프를 보면 A와 C가 연결되어 있고, A에서 B만 탐색했으니 C도 탐색해 주면 될 듯해 보인다.

그럼 어떻게 해야지 C로 갈 수 있을까?

 

방법은 현재 실행을 종료하고, 자신을 탐색하기 전인 정점을 따라 올라가는 것이다.

이때 이를 우리는 재귀라는 방법을 이용해 구현할 수 있다.

 

재귀 함수는 

def f():
	f()

 

이렇게 f라는 함수에서 다시 f를 호출하는 것을 말하는데,

A라는 정점에서 B라는 정점으로 탐색하기 위해 B로 시작하는 탐색 코드를 실행하고, B라는 정점이 탐색을 끝내면 다시 A로 돌아오도록 코드를 작성해 주면

우리는 그림 5에서 A-B-D-H-E를 거치고, E에서 H로, D, B, A로 다시 돌아갈 수 있다.

이제 아까와 같은 방법을 C에서도 진행해 주면 된다.

 

이렇게 A-B-D-H-E-C-F-G의 순으로 탐색이 완료되었다. 

이렇게 그래프에서 자신과 이웃한 정점으로 먼저 탐색을 진행하는 방식을 깊이 우선 탐색(DFS)라고 한다.

 

n=int(input())
m=int(input())
for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
check=[0]*n
graph[[]for i in range(n)]
def dfs(v):
    if check[v]!=0:return
    check[v]=1
    print(v)
    for i in range(len(graph[v])):
        if check[graph[v][i]]==0:
            dfs(graph[v][i])


dfs(1)

 

DFS를 코드로 나타내보면 이렇다.

N은 정점의 개수, M은 간선의 개수이다. 

Graph는 연결된 두 정점을 나타내며, 만약 a와 b가 연결되어 있다면 graph [a]. append(b) 이렇게 작성해 준다.

위 코드에서 graph [a]. append(b)와 graph [b]. append(a)를 해준 이유는 그래프에 방향이 없기 때문에 두 방향 모두 추가해 주었다. 만약 방향이 존재한다면 해당하는 방향만 추가해 주면 된다.

 

그리고 dfs라는 함수를 생성하고, check라는 리스트를 통해 만약 방문한 적 있다면 1, 아니면 0으로 설정하여 방문한 적이 있으면 탐색을 진행하지 않고, 방문한 적이 없다면 탐색을 진행한다.

 

이렇게 dfs를 알아봤다.

dfs는 그래프의 기본이라고 할 정도로 엄청나게 많이 쓰이는 알고리즘으로, 그래프 나오는 알고리즘 문제라고 한다면 기본 베이스로 dfs를 구현하고 진행한다.