[Unity C#] DFS(Depth First Search Algorithm) : 깊이 우선 탐색

개념

BFS와는 다르게 루트 노드 혹은 임의의 노드와 인접한 노드를 모두 탐색하는 것이 아니라, 연결된 정점들을 차례대로 한번씩 방문하는 알고리즘이다. 즉, 이름과 같이 넓게 탐색하기 이전에 깊게 탐색하는 알고리즘이다.

과정

 

장점

장점으로는, 현 경로상의 노드들만 기억하면 되므로 그래프의 높이 만큼의 공간만을 요구합니다. 따라서 최대 저장공간의 수요가 비교적 적습니다. 또한, 목표노드가 깊은 단계에 있을 경우에 해를 빠르게 구할 수 있습니다.

단점

단점으로는, 해가 없는 경로에 깊이 빠질 가능성이 있다는 것입니다. 또한 얻어진 해가 최단 경로가 된다는 보장이 없습니다. (목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이 때 얻어진 해는 최적의 해가 아닐 수 있습니다.)

시간복잡도

- 인접 행렬 : O(V^2)

DFS 하나에 for loop을 V 만큼 돌기 때문에, O(V) 시간이 필요함.

정점을 방문할 때 마다 DFS를 부르는데, V개의 정점을 모두 방문하므로

DFS의 전체 시간복잡도 = V * O(V) = O($V^2$)

쉽게 생각해서, 2차원 배열의 인덱스들을 한번씩 모두 탐색해야 하므로 $V^2$

- 인접 리스트 : O(V+E)

DFS는 총 V번 부르게 된다. 그러나, 인접 행렬로 구현한 경우와 달리 인접 리스트로 구현한 DFS는 DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 DFS 하나의 수행 시간이 일정하지 않다.

전체 DFS가 다 끝난 이후를 생각해 보면, DFS가 다 끝났을 시점에는 모든 정점을 한번씩 방문하고, 모든 간선을 한번씩 검사하게 되므로 O(V+E)의 시간이 걸린다고 말할 수 있다.

따라서, 인접리스트로 구현할 경우 DFS의 시간 복잡도는 O(V+E)이다.

소스코드 - 인접행렬, 재귀

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DepthFirstSearch_Source : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
        int n = 4; // 정점의 개수
        int m = 5; // 간선의 개수
        int v = 1; // 시작 정점

        int[,] arr = new int[n+1,n+1]; //1부터 시작하므로 +1
        bool[] c = new bool[n+1]; // 방문한 정점인지 아닌지 1차원으로 표현
                                  // ex) 1정점은 방문함 2정점은 방문 안함 ..

	//양방향 그래프니까
        alist[5].Add(4);
        alist[4].Add(5);

        alist[5].Add(2);
        alist[2].Add(5);

        alist[1].Add(2);
        alist[2].Add(1);

        alist[3].Add(4);
        alist[4].Add(3);

        alist[3].Add(1);
        alist[1].Add(3);

        dfs_Recursive(arr,c,v);
        dfs_stack(arr, c, v, false);

    }

    // 재귀 dfs_Recursive - 인접행렬
    void dfs_Recursive(int[,] arr, bool[] c, int v) // v를 방문하고 연결된 정점을 향해 가자 
    {
        int n = arr.GetLength(0)-1;

        c[v] = true; // 방문한 노드 1~4를 true로 변환
        Debug.Log(v + " "); // 방문한 정점을 출력한다 

        for (int i = 1; i <= n; i++) // 1~4까지의 노드
        {

            if (arr[v,i] == 1 && !c[i]) // arr[1,1~4] 중에 1이고 c[1~4]가 false면 재귀 
                                        // 즉 연결되어 있는데 아직 false인 정점이라면 방문하자
                                        // arr[v,i]때문에 연결된 정점을 끝까지 탐색하는 dfs_Recursive가 된다
            {
                dfs_Recursive(arr, c, i); // 방문하자 
            }
        }
    }
}

소스코드 - 인접행렬, Stack

// 스택 DFS - 인접행렬
    void dfs_stack(int[,] arr, bool[] c, int v, bool flag)
    {
        Stack<int> stack = new Stack<int>();
        int n = arr.GetLength(0) - 1;

        stack.Push(v); // stack에 쌓는다(방문함)
        c[v] = true; // 방문 checking 
        Debug.Log(v + " ");
       
        while (stack.Count != 0) // stack이 비어있지 않다면 돌아감 계속 pop되다보면 종료 
        {
            int vv = stack.Peek(); // stack의 Top데이터를 제거하지 않고 반환
                                   // pop되면 값이 바뀜 

            flag = false;

            for (int i = 1; i <= n; i++)
            {
                //마지막으로 방문한 정점(vv)과 연결된 정점(i)들중 아직 방문하지 않은 노드가 있는지 본다

                if (arr[vv,i] == 1 && !c[i]) // vv와 연결된 i노드들이 연결되어있고 방문하지 않았다면
                {
                    stack.Push(i); // i노드를 쌓는다(방문함)

                    c[i] = true; // 방문했으므로 check
                    flag = true; // 
                    break;
                }
            }

            if (!flag) // flag가 true가 아니란 것은 연결된 노드들을 모두 방문했다는 것
                       // 즉 Pop해서 이전 노드부터 다시 수행함(backtracking)

            {
                stack.Pop();
            }
        }
    }

소스코드 - 인접리스트, 재귀

public class DepthFirstSearch_Source : MonoBehaviour
{
    // Start is called before the first frame update
    void Start()
    {
        int n = 5; // 정점의 개수
        int m = 5; // 간선의 개수
        int v = 3; // 시작 정점


        ArrayList[] alist = new ArrayList[n + 1]; //Collection.ArrayList[]를 이용하여
        					//각 배열에 Arraylist Class를 객체화한다.
        bool[] c = new bool[n + 1];

        for(int i = 1; i < n+1; i++)
        {
            alist[i] = new ArrayList();
        }

        //간선의 개수 5개 input으로하면 for문으로 m까지
        //양방향 그래프        
        alist[5].Add(4);
        alist[4].Add(5);

        alist[5].Add(2);
        alist[2].Add(5);

        alist[1].Add(2);
        alist[2].Add(1);

        alist[3].Add(4);
        alist[4].Add(3);

        alist[3].Add(1);
        alist[1].Add(3);

        for(int i = 1; i < n+1; i++)
        {
            alist[i].Sort(); // 작은 값부터 먼저 방문하도록 정렬
        }

        dfs(alist, c, v);
     }
     
     // DFS 인접리스트
    void dfs(ArrayList[] a, bool[] c, int v)
    {

        if (c[v])
        {
            return;
        }

        c[v] = true;
        Debug.Log(v + " ");


        foreach (int vv in a[v]) // 해당(v)배열에 저장된 인접리스트들을 모두 탐색한다 
        {
            if (!c[vv]) //인접리스트 값 중 한 노드를 방문하지 않았다면 
            {
                dfs(a, c, vv);//방문한다 
                              //또 다시, 방문한 노드의 인접리스트를 탐색하면서 반복한다 
            }
        }
    }
 }