깊이 우선 탐색

4/8/2023
12 minutes to read

깊이 우선 탐색(Depth-First Search, DFS)은 그래프나 트리에서 노드를 방문하는 전략 중 하나로, 시작 노드에서 목표 노드를 찾을 때까지 가능한 한 깊게 탐색합니다. 이 방법은 노드의 모든 자식을 방문하기 전에 한 경로를 완전히 탐색합니다. 이 과정에서 방문한 노드를 기록하여 이미 방문한 노드를 다시 방문하지 않도록 합니다.

C# 언어에서 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘을 구현하는 간단한 예제를 아래에 제공합니다. 이 예제에서는 인접 리스트를 사용하여 그래프를 표현하고 있습니다.

코드: DepthFirstSearchExample.cs

namespace VisualAcademy
{
    using System;
    using System.Collections.Generic;

    class Graph
    {
        private int numVertices; // 정점의 개수
        private List<int>[] adjList; // 인접 리스트를 사용한 그래프 표현

        // 생성자: 정점의 개수를 인자로 받아 초기화
        public Graph(int numVertices)
        {
            this.numVertices = numVertices;
            adjList = new List<int>[numVertices];
            for (int i = 0; i < numVertices; i++)
            {
                adjList[i] = new List<int>();
            }
        }

        // 간선 추가 메서드: 두 정점 u, v를 인자로 받아 간선을 추가
        public void AddEdge(int u, int v)
        {
            adjList[u].Add(v);
        }

        // 깊이 우선 탐색의 보조 메서드 (재귀적)
        private void DFSUtil(int vertex, bool[] visited)
        {
            visited[vertex] = true; // 정점을 방문한 것으로 표시
            Console.WriteLine("방문한 노드: " + vertex);

            // 인접한 정점들을 순회하며 방문하지 않은 정점에 대해 재귀 호출
            foreach (int adjacent in adjList[vertex])
            {
                if (!visited[adjacent])
                {
                    DFSUtil(adjacent, visited);
                }
            }
        }

        // 깊이 우선 탐색 메서드: 시작 정점을 인자로 받아 실행
        public void DFS(int startVertex)
        {
            bool[] visited = new bool[numVertices]; // 방문한 정점을 기록하는 배열
            DFSUtil(startVertex, visited); // 깊이 우선 탐색 실행
        }
    }

    class DepthFirstSearchExample
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph(6); // 6개의 정점을 가진 그래프 객체 생성

            // 간선 추가
            graph.AddEdge(0, 1);
            graph.AddEdge(0, 2);
            graph.AddEdge(1, 3);
            graph.AddEdge(1, 4);
            graph.AddEdge(2, 4);
            graph.AddEdge(2, 5);

            graph.DFS(0); // 시작 정점을 0으로 설정하고 깊이 우선 탐색 실행
        }
    }
}

방문한 노드: 0
방문한 노드: 1
방문한 노드: 3
방문한 노드: 4
방문한 노드: 2
방문한 노드: 5

위 코드에서 Graph 클래스는 그래프를 표현하고, DFS 메서드를 사용하여 깊이 우선 탐색을 수행합니다. DFSUtil 메서드는 재귀적으로 깊이 우선 탐색을 구현하며, 방문한 노드를 visited 배열에 표시하여 이미 방문한 노드를 다시 방문하지 않습니다. Main 메서드에서 그래프를 생성하고 간선을 추가한 뒤, 시작 노드를 지정하여 깊이 우선 탐색을 수행합니다.

C 언어에서 깊이 우선 탐색 알고리즘을 구현하려면, 재귀 함수를 사용하거나 명시적 스택을 사용하여 노드를 방문할 수 있습니다. 다음은 간단한 예시입니다:

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 10

bool visited[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];

void dfs(int vertex, int num_vertices) 
{
    visited[vertex] = true;
    printf("방문한 노드: %d\n", vertex);

    for (int i = 0; i < num_vertices; i++) 
    {
        if (graph[vertex][i] && !visited[i]) 
        {
            dfs(i, num_vertices);
        }
    }
}

int main(void) 
{
    int num_vertices = 6;
    // 간선 표현 (인접 행렬)
    int edges[6][6] = 
    {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 1, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 0},
        {0, 1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0}
    };

    // 그래프 초기화
    for (int i = 0; i < num_vertices; i++) 
    {
        for (int j = 0; j < num_vertices; j++) 
        {
            graph[i][j] = edges[i][j];
        }
    }

    // 모든 정점을 방문하지 않은 상태로 초기화
    for (int i = 0; i < num_vertices; i++) 
    {
        visited[i] = false;
    }

    // 시작 정점을 0으로 설정하고 깊이 우선 탐색 실행
    dfs(0, num_vertices);

    return 0;
}

위 코드는 인접 행렬을 사용하여 그래프를 표현하고 있으며, 깊이 우선 탐색 알고리즘을 사용하여 그래프의 노드를 방문합니다. 방문한 노드는 visited 배열에 표시되어 이미 방문한 노드를 다시 방문하지 않습니다.

Java 언어에서 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘을 구현하는 간단한 예제를 아래에 제공합니다. 이 예제에서는 인접 리스트를 사용하여 그래프를 표현하고 있습니다.

코드: DepthFirstSearchExample.java

import java.util.ArrayList;
import java.util.List;

class Graph {
    private int numVertices; // 그래프의 정점 개수
    private List<Integer>[] adjList; // 그래프를 표현하는 인접 리스트

    // 생성자: 지정된 정점 개수로 그래프 초기화
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new ArrayList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    // 간선 추가 메서드: 두 정점(u, v) 사이에 간선을 추가
    public void addEdge(int u, int v) {
        adjList[u].add(v);
    }

    // 깊이 우선 탐색의 재귀적 보조 메서드
    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true; // 정점을 방문한 것으로 표시
        System.out.println("방문한 노드: " + vertex);

        // 인접한 정점들을 순회하며 방문하지 않은 정점에 대해 재귀 호출
        for (int adjacent : adjList[vertex]) {
            if (!visited[adjacent]) {
                dfsUtil(adjacent, visited);
            }
        }
    }

    // 깊이 우선 탐색 메서드: 지정된 정점에서 깊이 우선 탐색을 수행
    public void dfs(int startVertex) {
        boolean[] visited = new boolean[numVertices]; // 방문한 정점을 기록하는 배열
        dfsUtil(startVertex, visited); // 깊이 우선 탐색 시작
    }
}

public class DepthFirstSearchExample {
    public static void main(String[] args) {
        Graph graph = new Graph(6); // 6개의 정점을 가진 그래프 객체 생성

        // 간선 추가
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);

        graph.dfs(0); // 정점 0에서 시작하는 깊이 우선 탐색 수행
    }
}

방문한 노드: 0
방문한 노드: 1
방문한 노드: 3
방문한 노드: 4
방문한 노드: 2
방문한 노드: 5

위 코드에서 Graph 클래스는 그래프를 표현하고, dfs 메서드를 사용하여 깊이 우선 탐색을 수행합니다. dfsUtil 메서드는 재귀적으로 깊이 우선 탐색을 구현하며, 방문한 노드를 visited 배열에 표시하여 이미 방문한 노드를 다시 방문하지 않습니다. main 메서드에서 그래프를 생성하고 간선을 추가한 뒤, 시작 노드를 지정하여 깊이 우선 탐색을 수행합니다.

파이썬으로 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘을 구현한 코드는 다음과 같습니다.

코드: graph_dfs.py

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices  # 정점의 개수
        self.adj_list = [[] for _ in range(num_vertices)]  # 인접 리스트를 사용한 그래프 표현

    def add_edge(self, u, v):
        self.adj_list[u].append(v)  # 간선 추가 메서드: 두 정점 u, v를 인자로 받아 간선을 추가

    def _dfs_util(self, vertex, visited):
        visited[vertex] = True  # 정점을 방문한 것으로 표시
        print(f"방문한 노드: {vertex}")

        # 인접한 정점들을 순회하며 방문하지 않은 정점에 대해 재귀 호출
        for adjacent in self.adj_list[vertex]:
            if not visited[adjacent]:
                self._dfs_util(adjacent, visited)

    def dfs(self, start_vertex):
        visited = [False] * self.num_vertices  # 방문한 정점을 기록하는 리스트
        self._dfs_util(start_vertex, visited)  # 깊이 우선 탐색 실행

if __name__ == "__main__":
    graph = Graph(6)  # 6개의 정점을 가진 그래프 객체 생성

    # 간선 추가
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(1, 3)
    graph.add_edge(1, 4)
    graph.add_edge(2, 4)
    graph.add_edge(2, 5)

    graph.dfs(0)  # 시작 정점을 0으로 설정하고 깊이 우선 탐색 실행

방문한 노드: 0
방문한 노드: 1
방문한 노드: 3
방문한 노드: 4
방문한 노드: 2
방문한 노드: 5

이 코드에서 Graph 클래스는 그래프를 표현하고, dfs 메서드를 사용하여 깊이 우선 탐색을 수행합니다. _dfs_util 메서드는 재귀적으로 깊이 우선 탐색을 구현하며, 방문한 노드를 visited 리스트에 표시하여 이미 방문한 노드를 다시 방문하지 않습니다. 메인 코드에서 그래프를 생성하고 간선을 추가한 뒤, 시작 노드를 지정하여 깊이 우선 탐색을 수행합니다.

C++로 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘을 구현한 코드는 다음과 같습니다.

코드: DepthFirstSearchExample.cpp

#include <iostream>
#include <vector>

class Graph {
    int numVertices; // 정점의 개수
    std::vector<std::vector<int>> adjList; // 인접 리스트를 사용한 그래프 표현

public:
    // 생성자: 정점의 개수를 인자로 받아 초기화
    Graph(int numVertices) : numVertices(numVertices), adjList(numVertices) {}

    // 간선 추가 메서드: 두 정점 u, v를 인자로 받아 간선을 추가
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    // 깊이 우선 탐색의 보조 메서드 (재귀적)
    void DFSUtil(int vertex, std::vector<bool>& visited) {
        visited[vertex] = true; // 정점을 방문한 것으로 표시
        std::cout << "방문한 노드: " << vertex << std::endl;

        // 인접한 정점들을 순회하며 방문하지 않은 정점에 대해 재귀 호출
        for (int adjacent : adjList[vertex]) {
            if (!visited[adjacent]) {
                DFSUtil(adjacent, visited);
            }
        }
    }

    // 깊이 우선 탐색 메서드: 시작 정점을 인자로 받아 실행
    void DFS(int startVertex) {
        std::vector<bool> visited(numVertices, false); // 방문한 정점을 기록하는 벡터
        DFSUtil(startVertex, visited); // 깊이 우선 탐색 실행
    }
};

int main() {
    Graph graph(6); // 6개의 정점을 가진 그래프 객체 생성

    // 간선 추가
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 4);
    graph.addEdge(2, 5);

    graph.DFS(0); // 시작 정점을 0으로 설정하고 깊이 우선 탐색 실행

    return 0;
}

위 코드에서 Graph 클래스는 그래프를 표현하고, DFS 메서드를 사용하여 깊이 우선 탐색을 수행합니다. DFSUtil 메서드는 재귀적으로 깊이 우선 탐색을 구현하며, 방문한 노드를 visited 벡터에 표시하여 이미 방문한 노드를 다시 방문하지 않습니다. main 함수에서 그래프를 생성하고 간선을 추가한 뒤, 시작 노드를 지정하여 깊이 우선 탐색을 수행합니다.

추천 자료: .NET Blazor에 대해 알아보시겠어요? .NET Blazor 알아보기를 확인해보세요!