[Algorithm][그래프] 깊이우선탐색(DFS, Depth First Search)

깊이우선탐색(DFS)

이번 포스트에서는 그래프 탐색 알고리즘 중 하나인 깊이우선탐색(DFS)에 대해서 알아보겠습니다.

깊이우선탐색(DFS)이란?

< 깊이우선탐색(DFS) 과정 >

• 그래프에서 한 방향으로 가능한 깊이까지 계속 탐색 -> 더 이상 갈 수 없으면 다시 돌아와서 다른 방향을 탐색하는 방식의 그래프 순회 알고리즘입니다.
• 스택(Stack) 자료구조의 동작 원리(LIFO)를 따릅니다. -> 재귀 함수 또는 명시적 스택으로도 구현 가능
• 수도 코드(Pseudo Code)

u: 현재 탐색 중인 정점
v: u의 인접한 정점
adj[u]: 정점 u에 인접한 모든 정점들의 리스트
visited: 각 정점의 방문 여부를 기록하는 배열 또는 집합

DFS(u):
    visited[u] ← true       // 시작 정점 u 방문 표시
    u 처리                        // 정점 u 처리 (예: 출력, 결과 저장 등)

    for each v in adj[u]:  // u의 모든 인접 정점 v에 대해
        if not visited[v]:   // v를 아직 방문하지 않았다면
            DFS(v)              // v에 대해 DFS 재귀 호출

깊이우선탐색 구현 방법

1. 재귀함수 호출 전, 방문여부 확인

const int N = 4;
int visited[N];
vector<int> adj[N];

void dfs(int u) {
    visited[u] = true;

    for (int v: adj[u]) {
        if(visited[v]) continue; // 인접 정점 방문여부 확인
        dfs(v);
    }
}

 

2. 재귀함수 호출 후, 방문여부 확인

const int N = 4;
int visited[N];
vector<int> adj[N];

void dfs(int u) {
    if (visited[u]) // 시작 정점 방문여부 확인
        return;

    visited[u] = true;
    for (int v: adj[u]) {
        dfs(v);
    }
}

 

문제에 따라 각각의 구현 방법이 유용할 때가 있으므로 2가지 코드 모두 이해하고 구현하는 것이 중요합니다.

깊이우선탐색의 특징

항목	설명
시간복잡도	\(O(V + E)\) (정점 + 간선 개수)
자료구조	스택 (또는 재귀 호출 스택)
사용 예시	미로 찾기, 백트래킹 문제, 사이클 검출, 위상 정렬 등
구현 방식	재귀 함수 또는 명시적 스택 사용

 

⚠️ 주의할 점

• 무한 루프 방지를 위해 visited 체크는 꼭 필요합니다.
• 방향 그래프일 경우 방향에 맞게만 탐색해야 합니다.
• 연결되지 않은 그래프의 모든 정점을 탐색하려면 반복문으로 모든 정점 시작 DFS 수행이 필요합니다.

깊이우선탐색 예제

1. 미로탈출

• 설명
  • N × M 크기의 미로에서 출발점에서 도착점까지 갈 수 있는지 판별하는 문제
  • 이동은 상하좌우 인접한 칸으로만 가능하며, 이동할 수 있는 칸은 1로 표시되어 있습니다. 또한, 벽은 0으로 표시되어 있습니다.
  • 출발점(0, 0)에서 도착점(N-1, M-1)까지 도달 가능하면 '도착 가능', 불가능하다면 '도착 불가능' 출력

• 입력 예시

5 6
1 0 1 0 1 0
1 1 1 1 1 0
0 0 0 0 1 0
1 1 1 0 1 0
0 0 1 1 1 1

• 출력 예시

도착 가능

• 아이디어
  • 1은 이동 가능한 칸, 0은 벽
  • DFS로 (0, 0)에서 시작해서 (N-1, M-1)에 도달할 수 있는지 확인
  • 상하좌우 방향으로 이동하며 방문 체크

• 정답 코드

#include <bits/stdc++.h>
using namespace std;

const int N = 5, M = 6;
int maze[N][M] = {
    {1, 0, 1, 0, 1, 0},
    {1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 1, 0},
    {1, 1, 1, 0, 1, 0},
    {0, 0, 1, 1, 1, 1}
};
bool visited[N][M];

int dx[] = {-1, 1, 0, 0}; // 상하좌우
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= M) return false;
    if (maze[x][y] == 0 || visited[x][y]) return false;

    visited[x][y] = true;
    if (x == N - 1 && y == M - 1) return true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (dfs(nx, ny)) return true;
    }

    return false;
}

int main() {
    if (dfs(0, 0)) cout << "도착 가능" << "\n";
    else cout << "도착 불가능" << "\n";
    return 0;
}

 

2. 연결 요소의 개수 구하기

• 설명
  • 무방향 그래프가 주어졌을 때, 그래프의 연결 요소가 몇 개인지 출력하는 문제

• 입력 예시
  • 첫 줄에는 정점의 개수(N)와 간선의 개수(M)이 주어집니다.
  • 두번째 줄부터 두 개의 연결된 정점이 각각 주어집니다.

6 5
1 2  
2 5  
5 1  
3 4  
4 6

• 출력 예시

2

• 아이디어
  • DFS로 방문 가능한 모든 노드를 순회
  • 방문하지 않은 노드에서 DFS를 새로 시작하면 연결 요소 +1

• 정답 코드

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1001;
vector<int> adj[MAX];
bool visited[MAX];
int N = 6, M = 5;

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v])
            dfs(v);
    }
}

int main() {
    vector<pair<int, int>> edges = {
        {1, 2}, {2, 5}, {5, 1}, {3, 4}, {4, 6}
    };

    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 무방향 그래프
    }

    int components = 0;
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
            components++;
        }
    }

    cout << "연결 요소 개수: " << components << "\n";
    return 0;
}

마무리하며

• 지금까지 DFS 개념에 대해 알아보며 DFS는 한 정점에서 시작해 가능한 한 깊이 들어갔다가 더 이상 갈 곳이 없으면 되돌아오는 방식으로 동작한다는 점을 이해했습니다.
• 재귀 호출 또는 스택을 이용해 구현할 수 있으며 이를 통해 그래프 내의 연결성 확인, 경로 탐색, 사이클 여부 판단 등 다양한 문제를 해결할 수 있습니다.
• DFS를 확실히 이해하면 이후 배우게 될 BFS(너비 우선 탐색), 위상 정렬, 트리 탐색, 강한 연결 요소 등의 개념도 쉽게 이해할 수 있습니다.
• 다음 글에서는 DFS와 쌍을 이루는 BFS(너비 우선 탐색)에 대해 다뤄볼 예정입니다.