[알고리즘] DFS(깊이 우선 탐색)

📌 Intro

그래프 탐색의 기본은 BFS와 DFS다. 그 중 DFS에 대해 알아보도록 하자.

📌 DFS(깊이 우선 탐색)

DFS는 Depth-First Search로 깊이 우선 탐색이다. 시작 노드로부터 계속 갈 수 있을 때까지 탐색을 진행하다 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행하는 방법이다.
모든 노드를 방문하고자 하는 경우 DFS를 사용하는데 이전에 다루었던 BFS보다 구현 방법이 간단하지만 단순 검색 속도 자체로만 보면 BFS가 더 빠르다.
DFS를 구현하기 위해서는 스택(Stack)이라는 자료구조를 사용한다.

 

DFS의 동작 과정은 다음과 같다.

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

STEP 0

다음과 같은 그래프에서 DFS가 어떻게 동작하는지 알아보도록 하자. 이 때 방문 처리된 노드는 회색으로, 현재 처리하는 스택의 최상단 노드는 하늘색으로 표현하도록 하겠다.
일반적으로 그래프를 탐색할 때 방문하지 않은 노드가 여러개라면 작은 번호부터 처리한다.

STEP 1

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

 

STEP 2

스택의 최상단 노드인 1번 노드와 인접하고 방문하지 않은 노드는 4번, 6번 노드가 있다. 이 중 가장 작은 번호인 4번 노드를 스택에 추가하고 방문 처리를 한다.

 

STEP 3

스택의 최상단 노드인 4번 노드와 인접하고 방문하지 않은 노드는 3번 노드다. 3번 노드를 스택에 추가하고 방문 처리를 한다.

 

STEP 4

스택의 최상단 노드인 3번 노드와 인접하고 방문하지 않은 노드는 없다. 따라서 스택에서 3번 노드를 꺼낸다.

 

STEP 5

스택의 최상단 노드인 4번 노드와 인접하고 방문하지 않은 노드는 없다. 따라서 스택에서 4번 노드를 꺼낸다.

 

STEP 6

스택의 최상단 노드인 1번 노드와 인접하고 방문하지 않은 노드는 6번 노드다. 6번 노드를 스택에 추가하고 방문 처리를 한다.

 

STEP 7

스택의 최상단 노드인 6번 노드와 인접하고 방문하지 않은 노드는 5번 노드다. 5번 노드를 스택에 추가하고 방문 처리를 한다.

 

STEP 8

스택의 최상단 노드인 5번 노드와 인접하고 방문하지 않은 노드는 2번 노드다. 2번 노드를 스택에 추가하고 방문 처리를 한다.

 

STEP 9

스택의 최상단 노드인 2번 노드와 인접하고 방문하지 않은 노드는 없다. 또 방문하지 않은 노드는 더 이상 없다. 따라서 스택에서 차례대로 꺼내고 DFS를 종료한다.
DFS를 이용하여 그래프를 방문한 순서는 다음과 같다.

 

📌 DFS 구현

#include <iostream>
#include <vector>
using namespace std;

bool visited[7];
vector<int> graph[7];

void DFS(int start){
    visited[start] = true;

    // 현재 노드에서 방문이 가능한 노드 확인
    for(int i=0; i<graph[start].size(); i++){
        int next = graph[start][i];

        if(visited[next] == false){
            DFS(next);  // DFS 재귀적 호출
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    graph[1].push_back(4);
    graph[4].push_back(1);

    graph[1].push_back(6);
    graph[6].push_back(1);

    graph[2].push_back(5);
    graph[5].push_back(2);

    graph[3].push_back(4);
    graph[4].push_back(3);

    graph[5].push_back(6);
    graph[6].push_back(5);

    DFS(1);

    return 0;
}

 

📌 관련 문제

1260번: DFS와 BFS

2667번: 단지번호붙이기

📌 참고

[1] 이것이 취업을 위한 코딩 테스트다 with 파이썬