[C#] DFS(깊이 우선 탐색)

DFS란?

-Depth First Search의 약자로 깊이 우선 탐색이라고 불립니다.  DFS를 예로 들어 용감한 전사 한명이 모든 보스 방을 클리어 하기위해 무조건 보이는 방을 직진해서 들어갑니다. 그러다가 길이 막히면 다시 다른 방을 찾기위해 되돌아와서 다른 방까지 클리어하게 됩니다.  DFS는 스택 or 재귀함수로 구현하는데 대부분 재귀함수를 이용하여 구현합니다. 재귀함수를 이용할때에는 연결되어 있는지와 이미 방문했는지에 대한 여부를 꼭 프로그래밍 해주어야 합니다.

 

두가지 구현 방법을 예제로 작성해보겠습니다. (결과는 같습니다.)

1) 행렬을 이용한 DFS

2) List를 이용한 DFS

 

1) 행렬을 이용한 DFS

using System;
using System.Collections.Generic;

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

        bool[] visited = new bool[6];
        //1) 우선 now부터 방문
        //2) now와 연결된 정점들을 하나씩 확인해서, 아직 미발견(미방문) 상태라면 방문한다.
        public void DFS(int now)
        {
            Console.WriteLine(now);
            visited[now] = true; //1) 우선 now 부터 방문

            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);
        }
    }
}

graph.DFS(0)일때

graph.DFS(0)일때

graph.DFS(0)일때

 

graph.DFS(1)일때

graph.DFS(1)일때

 

graph.DFS(1)일때

 

2) List를 이용한 DFS

using System;
using System.Collections.Generic;

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


        bool[] visited = new bool[6];
        public void DFS2(int now)
        {
            Console.WriteLine(now);
            visited[now] = true; //1) 우선 now 부터 방문

            foreach (int next in adj2[now]) //연결되어 있지 않으면 스킵
            {
                if (visited[next]) //이미 방문 했으면 스킵
                    continue;
                DFS2(next);
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.DFS2(0);
        }
    }
}

 

 

 

---------------------------------------------------------------------------------------------------------------------------

참고 : [인프런] Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘