DFS [C#]

그래프 탐색의 기본 중의 하나이다.

사실 어떻게 동작하는지는 알았으나 정확하게 구현은 잘 못했었다.

이참에 어떻게 구현해야 하는지 배워보았다.

 

그래프 탐색

---

그래프 탐색 알고리즘 중 대표적으로 사용되는 DFS에 대해서 알아본다.

그래프 탐색은 그래프 내 임의의 한 정점(Vertex)에서 시작해서 모든 정점(Vertexs)들을 탐색하는 것을 말한다.

DFS(Depth-First Searsh)는 현재 정점에서 최대 깊이까지 들어가면서 탐색하는 것이고, 이거랑 다른 대표적인 그래프 탐색 기법에는 BFS(Breadth-First Search)가 있다. 너비 우선 탐색은 다음 시간에 알아보기로 하자!

 

코드로 먼저 보여주면 다음과 같다.

using System;
using System.IO;
using System.Collections.Generic;

namespace AlgorithmProblem
{
    class DFS_Algorithm
    {

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            bool[] visited = new bool[8];

            List<int>[] graph = new List<int>[8];
            for (int i = 0; i < graph.Length; ++i)
            {
                graph[i] = new List<int>();
            }
            graph[0].Add(1);
            graph[1].Add(2);
            graph[1].Add(3);
            graph[2].Add(4);
            graph[2].Add(5);
            graph[3].Add(6);
            graph[3].Add(7);
            int target = 4;
            int count = 0;
            bool isSearch = false;

            dfs(visited, graph, 1, target, ref count, ref isSearch);

            //count = 0;
            //dfsStack(visited, graph, 1, target, ref count);

            sw.WriteLine(count);
            sw.Flush();
            sr.Close();
            sw.Close();
        }

        static void dfs(bool[] visited, List<int>[] graph, int x, int target, ref int count, ref bool isSearch)
        {
            visited[x] = true;
            ++count;

            if (x == target)
            {
                isSearch = true;
                return;
            }

            int y;
            for (int i = 0; i < graph[x].Count; ++i)
            {
                y = graph[x][i];
                if (visited[y] == false)
                {
                    dfs(visited, graph, y, target, ref count, ref isSearch);
                    if (isSearch == true)
                    {
                        break;
                    }
                }
            }
        }

        static void dfsStack(bool[] visited, List<int>[] graph, int x, int target, ref int count)
        {
            Stack<int> stack = new Stack<int>();
            stack.Push(x);
            ++count;

            int node;
            int nextNode;
            while (stack.Count != 0)
            {
                node = stack.Pop();
                if (node == target)
                {
                    break;
                }
                for (int i = 0; i < graph[node].Count; ++i)
                {
                    nextNode = graph[node][i];

                    if (visited[nextNode] == false)
                    {
                        visited[nextNode] = true;
                        ++count;
                        stack.Push(node);
                        stack.Push(nextNode);
                        break;
                    }
                }
            }
        }
    }
}

 

1. 첫번째로 지역과, 지역이 가지고 있는 경로들을 셋팅해주자.

이런식으로 1~7번까지의 위치가 존재하고

그 위치를 DFS를 통해 전부 통과를 해보자!!!

 

 

 

0번째 리스트는 안쓸거기 때문에!! 8개의 리스트와 visited[] 배열을 생성했다.

bool visited[] : 각 위치를 방문했는지에 대한 여부를 판별하는 bool 타입 배열

List<int> graph[] : 리스트 배열이다. 위치의 크기를 가진 리스트 배열이다.

각 리스트는 여러개의 위치를 가질 수 있으므로!!!

(예를 들어 1번째 위치는 2, 3과 연결되어 있으므로 인덱스 형태로 데이터를 가지고 있다.)

 

target : 이건 잠깐 무시! DFS는 기본적으로 탐색이므로 target을 탐색하려고 생성한 변수임.

count : 탐색을 할 때 최대 몇번 반복 하는지 체크하려고 만든 변수

isSearch : 재귀적으로 구현 하게되면 target을 찾았을 때 더이상 탐색하면 안되기 때문에 만들어준 변수

 

 

 

DFS [재귀적 이용]

 

심플하다!!!!!

참고로 전체 지역을 전부 방문한다고 했을 때 다음과 같이 코드를 작성 할 수 있;다.

처음 x 값으로 1이 들어온다.

 

(1)

1번째 지역을 방문하는것!

1번째 지역은 2번 지역과 3번 지역과 연결되어 있으므로(1번째 리스트에는 2, 3이 저장되어 있다)

graph[x][i]는 각각 2, 3이다.

y = 2가 들어오면

2번째 지역을 방문했는지 체크한다.

 

방문을 안했다면 방문해주자!

근대 이부분을 재귀적으로 호출해주는것이다.!!!

 

(2)

그러면 dfs를 다시 호출하게 된다.

이때 인자로 x 값으로 2를 넘겨주고

vistited, graph는 동일하다.

이를 반복하다보면 결국

가자 깊은 곳에 도달하게 된다.

 

(3)
여기서는 4번째 지역을 방문하게 되면

해당 4번째 리스트에는 연결된 지역이 없기 때문에(저장된 값이 없음)

for문을 돌지 않고 함수를 종료한다.

 

이게 기본원리이다 ㅎㅎ

 

보통 그러면 언제 사용할까???

 

사실 순수하게 방문이 목적인 경우는 없다.

보통은 연결된 지역들을 통해

내가 원하는 지역에 도달했을때 종료!!

즉 찾고자하는 값이 있다면 이때 종료를 한다.

 

 

 

 

이건 찾는 코드이다.

target : 찾고자 하는 값

count : 횟수

isSearch : 찾았을 때!!

 

 

DFS [스택 이용]

 

해당 코드는 전체 방문보다는 찾는 코드로 설명해 보겠다.

우선 첫번째 위치를 스택에 저장하고 카운트를 1 증가한다.(1번째 지역을 방문했기 때문에)

 

이후에 node와 nextNode가 있는데

node에는 현재 내가 있는 위치 인덱스라고 보면 되고

nextNode는 내가 다음에 방문 할 위치 인덱스라고 보면 된다.

 

stack.Count == 0이 의미하는 바는 이미 전부 방문했다고 볼 수 있다.

현재 node에 stack의 값을 pop해서 저장한다.

 

node가 내가 찾고자 하는 target이라면 그 즉시 함수를 종료하면 된다!!

for문을 반복 할 때 nextNode에는 다음 위치 인덱스가 들어간다고 했다.

 

그리고 나서 해당 지역을 방문했는지 검사한다.

만약 방문하지 않았다면 방문으로 체크하고 count를 하나 올린다.

이후 node와 nextNode를 넣어주면 끝!!!!!!