[Algorithm] 탐색 알고리즘 DFS

오도원공육사·2021년 7월 15일

DFS 그래프 탐색 알고리즘

알고리즘

목록 보기

12/17

출처. 이것이 취업을 위한 코딩테스트다 [나동빈]

DFS - Depth First Search

DFS는 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 보기 전에 그래프(Graph)의 기본 구조를 알아보자.

그래프

그래프는 정점(node, vertex)과 간선(Edge)으로 표현된다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 "두 노드는 인접하다(Adjacent)"라고 표현한다.

DFS

DFS는 탐색 알고리즘이다. 깊이 우선 탐색이므로 이 알고리즘은 특정한 경로로 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 구체적인 동작 과정은 다음과 같다.

탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 해당 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 써낸다.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

방문처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않도록 체크하는 것을 의미한다. 방문 처리를 통해 각 노드를 한 번씩만 처리할 수 있다.

예시

다음 그래프를 DFS 알고리즘으로 탐색해보자. 이때 탐색 시작 노드는 1번 노드이다. 인접 노드가 여러 개일 때는 일반적으로 번호가 낮은 것부터 우선한다.

step 1)

시작 노드 1을 스택에 넣고 방문처리한다.
스택 : [1]
방문 : 1

step 2)

스택의 최상단 노드 1에 방문하지 않은 인접 노드 2, 3, 8이 있다. 이 중 가장 작은 노드 2를 스택에 넣고 방문 처리한다.
스택 : [1, 2]
방문 : 1, 2

step 3)

스택 최상단 노드 2에 방문하지 않은 인접 노드 7을 스택에 넣고 방문처리한다.
스택 : [1, 2, 7]
방문 : 1, 2, 7

step 4)

스택 최상단 노드 7에 방문하지 않은 인접 노드 6, 8이 있다. 이 중 가장 작은 노드 6을 스택에 넣고 방문처리한다.
스택 : [1, 2, 7, 6]
방문 : 1, 2, 7, 6

step 5)

스택 최상단 노드 6에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 6을 꺼낸다.
스택 : [1, 2, 7]
방문 : 1, 2, 7, 6

step 6)

스택 최상단 노드 7에 방문하지 않은 인접 노드 8이 있다. 따라서 8번 노드를 스택에 넣고 방문 처리를 한다.
스택 : [1, 2, 7, 8]
방문 : 1, 2, 7, 6, 8

step 7)

스택 최상단 노드 8에 방문하지 않은 인접 노드가 없다. 따라서 8번 노드를 스택에서 꺼낸다.
스택 : [1, 2, 7]
방문 : 1, 2, 7, 6, 8

step 8)

스택 최상단 노드 7에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 7번 노드를 꺼낸다.
스택 : [1, 2]
방문 : 1, 2, 7, 6, 8

step 9)

스택 최상단 노드 2에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 2번 노드를 꺼낸다.
스택 : [1]
방문 : 1, 2, 7, 6, 8

step 10)

스택 최상단 노드 1에 방문하지 않은 인접 노드 3을 스택에 넣고 방문처리한다.
스택 : [1, 3]
방문 : 1, 2, 7, 6, 8, 3

step 11)

스택 최상단 노드 3에 방문하지 않은 인접 노드 4, 5 중에서 가장 작은 노드 4를 스택에 넣고 방문처리한다.
스택 : [1, 3, 4]
방문 : 1, 2, 7, 6, 8, 3, 4

step 12)

스택 최상단 노드 4에 방문하지 않은 인접 노드 5를 스택에 넣고 방문 처리한다.
스택 : [1, 3, 4, 5]
방문 : 1, 2, 7, 6, 8, 3, 4, 5

step 13)

남아 있는 노드에 방문하지 않은 인접 노드가 없으므로 차례대로 꺼낸다.

깊이 우선 탐색 알고리즘 DFS는 스택 자료구조에 기초한다. 실제로는 스택없이 재귀를 통해서 구현이 가능하다. 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.

소스코드

파이썬

def dfs(v):
    visited.add(v)
    print(v, end=' ')

    for i in graph[v]:
        if i not in visited:
            dfs(i)

visited = set()
graph = {
   1: [2, 3, 8], # 1번 노드에 2, 3, 8번 노드가 연결되어있다.
   2: [1, 7],
   3: [1, 4, 5],
   4: [3, 5],
   5: [3, 4],
   6: [7],
   7: [2, 6, 8],
   8: [1, 7]
}

dfs(1)

C언어

#include <stdio.h>
 
int graph[1001][1001]={0};
int visit[1001]={0};
 
void dfs(int v,int N){
    int i;
 
    visit[v]=1;
    printf("%d ",v);
    for(i=1;i<=N;i++){
        if(graph[v][i]==1 && visit[i]==0){
            dfs(i,N);
        }
    }
 
    return;
}
 
int main(){
    int N,M,start;
    int i,x,y;
 
    scanf("%d%d%d",&N,&M,&start);
    
    for(i=0;i<M;i++){
        scanf("%d%d",&x,&y);
        graph[x][y]=1;
        graph[y][x]=1;
    }
 
    dfs(start,N);
 
    return 0;
}