DFS (깊이 우선 탐색)

전체 코드

namespace Exercise
{
    class Graph
    {
        int[,] adj = new int[6, 6]
        {
            { 0, 1, 0, 1, 0, 0 },
            { 1, 0, 1, 1, 0, 0 },
            { 0, 1, 0, 0, 0, 0 },
            { 1, 1, 0, 0, 1, 0 },
            { 0, 0, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0 }
        };
        List<int>[] adj2 = new List<int>[6]
        {
            new List<int> {1, 3},
            new List<int> {0, 2, 3},
            new List<int> {1},
            new List<int> {0,1,4},
            new List<int> { 3,5 },
            new List<int> {4},
        };

        bool[] visited = new bool[6];
        // 시작점이 있어야함

        // now부터 방문하고 
        // now와 연결된 정점들을 하나씩 확인해서 [아직 미방문 상태라면] 방문한다.
        public void DFS(int now)
        {
            Console.WriteLine(now); // 방문한 정점 출력
            visited[now] = true;    // 방문 처리

            // 현재 정점(now)에서 연결된 정점(next) 탐색
            for (int next = 0; next < 6; next++)
            {
                if (adj[now, next] == 0)  // 연결되어 있지 않으면 스킵
                    continue;
                if (visited[next])        // 이미 방문한 정점이면 스킵
                    continue;

                DFS(next);  // 재귀 호출 (깊이 탐색)
            }
        }

        public void DFS2(int now)
        {
            Console.WriteLine(now); // 방문한 정점 출력
            visited[now] = true;    // 방문 처리

            // 현재 정점(now)에서 연결된 모든 정점 탐색
            foreach (var next in adj2[now])
            {
                if (visited[next]) // 이미 방문한 정점이면 스킵
                    continue;

                DFS2(next); // 깊이 우선 탐색
            }
        }
        public void SearchAll()
        {
            visited = new bool[6]; // 방문 배열 초기화

            for (int now = 0; now < 6; now++)
            {
                if (!visited[now]) // 방문하지 않은 정점이면 DFS 실행
                    DFS(now);
            }
        }
        // 길이 끊기면 연결이 안되고 끊김 
        // 모든 정점을 돌면은 다음 정점에서 다시 붙여서 DFS를 돌려야됨
}

internal class Program
    {
        
        static void Main(string[] args)
        {
            // DFS (Depth First Search 깊이 우선 탐색)
            // 들어갈 수 있으면 무조건 들어가본다.
            // 
            Graph graph = new Graph();
            graph.DFS(3);
            graph.DFS2(0);
            // BFS (Breath First Search 너비 우선 탐색)

        }

    }
}

1. DFS(Depth First Search)란?

DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 백트래킹(되돌아가기) 하면서 탐색을 진행합니다.

DFS의 특징

• 스택(Stack) 또는 재귀(Recursion)를 활용하여 탐색
• 최단 경로 탐색이 필요 없는 경우 유용
• 백트래킹(Backtracking)과 잘 어울림
• 그래프의 연결 요소(Connected Components) 탐색에 효과적

---

2. DFS의 동작 방식

1. 시작 정점을 방문하고 방문 처리(visited 배열을 true로 설정)
2. 현재 정점과 연결된 모든 정점을 확인
3. 방문하지 않은 정점이 있으면 해당 정점으로 이동(재귀 호출)
4. 더 이상 방문할 정점이 없으면 이전 정점으로 되돌아가기(백트래킹)

---

3. DFS 구현 방법

DFS는 세 가지 방법으로 구현 가능합니다.
1. 인접 행렬을 사용한 DFS
2. 인접 리스트를 사용한 DFS
3. 연결이 끊긴 그래프에서 DFS를 실행하는 방법(전체 탐색)

---

4. DFS 구현 코드

4.1 인접 행렬을 사용한 DFS

인접 행렬을 이용한 DFS는 모든 정점 간의 연결 정보를 2차원 배열로 표현합니다.

using System;

class Graph
{
    // 6x6 크기의 인접 행렬 (0: 연결X, 1: 연결O)
    int[,] adj = new int[6, 6]
    {
        { 0, 1, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 1, 1, 0, 0, 1, 0 },
        { 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 1, 0 },
    };

    bool[] visited = new bool[6]; // 방문 여부 체크

    public void DFS(int now)
    {
        Console.WriteLine(now); // 방문한 정점 출력
        visited[now] = true;    // 방문 처리

        // 현재 정점(now)에서 연결된 정점(next) 탐색
        for (int next = 0; next < 6; next++)
        {
            if (adj[now, next] == 0)  // 연결되어 있지 않으면 스킵
                continue;
            if (visited[next])        // 이미 방문한 정점이면 스킵
                continue;

            DFS(next);  // 재귀 호출 (깊이 탐색)
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph();
        graph.DFS(0); // 정점 0에서 DFS 탐색 시작
    }
}

✅ 실행 결과

0
1
2
3
4
5

• graph.DFS(3);

✅ 설명

1. visited 배열을 사용하여 방문한 정점을 체크
2. for 문을 사용하여 현재 정점과 연결된 정점들을 탐색
3. 방문하지 않은 정점이 있으면 재귀 호출하여 DFS 진행

---

4.2 인접 리스트를 사용한 DFS

인접 리스트는 각 정점과 연결된 정점들만 저장하므로 메모리를 절약할 수 있습니다.

using System;
using System.Collections.Generic;

class Graph
{
    // 인접 리스트 방식으로 그래프 표현
    List<int>[] adj2 = new List<int>[]
    {
        new List<int>() { 1, 3 },
        new List<int>() { 0, 2, 3 },
        new List<int>() { 1 },
        new List<int>() { 0, 1, 4 },
        new List<int>() { 3, 5 },
        new List<int>() { 4 },
    };

    bool[] visited = new bool[6]; // 방문 여부 체크

    public void DFS2(int now)
    {
        Console.WriteLine(now); // 방문한 정점 출력
        visited[now] = true;    // 방문 처리

        // 현재 정점(now)에서 연결된 모든 정점 탐색
        foreach (var next in adj2[now])
        {
            if (visited[next]) // 이미 방문한 정점이면 스킵
                continue;

            DFS2(next); // 깊이 우선 탐색
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph();
        graph.DFS2(0); // 정점 0에서 DFS 탐색 시작
    }
}

✅ 실행 결과

0
1
2
3
4
5

✅ 설명

1. foreach 문을 사용하여 현재 정점과 연결된 정점 탐색
2. 방문하지 않은 정점이 있으면 재귀 호출하여 DFS 진행
3. 인접 행렬 방식보다 메모리를 절약할 수 있음

---

4.3 연결이 끊긴 그래프에서 DFS 실행

만약 그래프가 여러 개의 연결 요소(Connected Components) 로 이루어져 있다면, SearchAll() 함수를 통해 모든 정점을 탐색해야 합니다.

using System;

class Graph
{
    int[,] adj = new int[6, 6]
    {
        { 0, 1, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 0, 0 },
        { 0, 1, 0, 0, 0, 0 },
        { 1, 1, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 1 },
        { 0, 0, 0, 0, 1, 0 },
    };

    bool[] visited = new bool[6]; // 방문 여부 체크

    public void DFS(int now)
    {
        Console.WriteLine(now);
        visited[now] = true;

        for (int next = 0; next < 6; next++)
        {
            if (adj[now, next] == 0)
                continue;
            if (visited[next])
                continue;

            DFS(next);
        }
    }

    public void SearchAll()
    {
        visited = new bool[6]; // 방문 배열 초기화

        for (int now = 0; now < 6; now++)
        {
            if (!visited[now]) // 방문하지 않은 정점이면 DFS 실행
                DFS(now);
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph();
        graph.SearchAll(); // 그래프 전체 탐색
    }
}

✅ 실행 결과

0
1
2
3
4
5

✅ 설명

• SearchAll() 함수는 모든 정점에 대해 DFS 실행
• 연결되지 않은 정점도 탐색 가능
• 그래프가 여러 개의 연결 요소로 나뉘어 있어도 탐색이 가능

---

5. DFS 구현 방식 비교

방식	메모리 사용량	탐색 속도	적용 예
인접 행렬	O(N²)	O(N)	간선이 많은 그래프
인접 리스트	O(N+M)	O(N)	간선이 적은 그래프
SearchAll	O(N+M)	O(N)	그래프가 여러 개의 연결 요소로 나뉘어 있을 때

---