Chapter 4-3. 그래프 순회 방법 1️⃣ - DFS(깊이 우선 탐색)

Date:     Updated:

카테고리:

태그:

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 4. 그래프

🚖 그래프 순회 방법

배열이나 리스트는 선형 자료 구조이므로 원소들을 차례대로 순회하면 되지만 그래프는 선형 자료 구조가 아닌, 한 정점에 연결된 정점들이 여러개일 수 있으므로 연결된 정점들 중 다음엔 어떤 정점을 탐색할지 다르므로 순회 방법이 다양하다. 대표적으로 두 가지가 있다.

  • 그래프 순회 방법
    1. DFS (Depth First Search 깊이 우선 탐색)
      • 들어갈 수 있다면 무조건 들어가며 깊이 들어감
      • 끝까지 들어가야 다시 돌아 옴
    2. BFS (Breadth First Search 너비 우선 탐색)


🚖 DFS

image

1️⃣ 배열로 구현된 그래프 DFS 순회

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

        bool[] visited = new bool[6]; // 방문 체크를 위해

        public void DFS(int now)  // 순회 시작 위치가 인수로 들어 옴
        {
            // 1) now 부터 방문 하고
            Console.WriteLine(now);
            visited[now] = true;

            // 2) 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(3);  // 3 0 1 2 4 5
        }
    }
  1. 일단 방문 체크를 한다.
  2. 연결이 되어 있으며, 아직 방문하지 않은 곳이라면 깊이 들어가 방문한다.
    • 배열은 연결 되어 있지 않은 정보도 포함되어 있기 때문에 (0) 연결 되어 있는지 즉 갈 수 있는지를 체크해주어야 한다.
    • 갈 수 있는 곳이라면 깊이 들어간다. 👉 재귀 함수 호출

DFS(3) 3 에서 DFS 순회를 시작했다면 3 0 1 2 4 5 순으로 방문하게 될 것이다.


2️⃣ 리스트로 구현된 그래프 DFS 순회

    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)
        {
            // 1) now 부터 방문 하고
            Console.WriteLine(now);
            visited[now] = true;

            // 2) 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);  // 0 1 2 3 4 5
        }
    }
  1. 일단 방문 체크를 한다.
  2. 아직 방문하지 않은 곳이라면 깊이 들어가 방문한다.
    • 리스트는 나와 연결 되어 있는 정보만 갖고 있기 때문에 연결 되어 있는지를 체크할 필요는 없다.
    • 갈 수 있는 곳이라면 깊이 들어간다. 👉 재귀 함수 호출

DFS2(0) 3 에서 DFS 순회를 시작했다면 0 1 2 3 4 5 순으로 방문하게 될 것이다.


3️⃣ 연결이 끊겨 있는 부분이 있는 그래프 DFS 순회

image

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

adj[3][4], adj[4][3] 값을 0 으로 바꾸어 3, 4 정점간의 연결을 끊어 준다.

    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) 
        {
            // ...
        }

        public void SearchAll()
        {
            visited = new bool[6];  // 전부 false로 초기화

            for (int now = 0; now < 6; now++)
            {
                if (visited[now] == false)
                    DFS(now);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();

            graph.SearchAll();  // 0 1 2 3 4 5
        }
    }
  • now = 0 👉 DFS(0)
    • 이 호출 하나가 끝났을 땐, visited[0], visited[1], visited[2], visited[3] 의 값은 true로 바뀌어 있다.
      • 0 을 시작으로 깊이 들어가 0, 1, 2, 3 정점을 모두 방문했기 때문.
        • now 값이 1, 2, 3 일땐 if (visited[now] == false) 걸리지 않는다. (생각보다 if문이 자주 호출되진 않음. DFS(0) 호출 한번으로 0, 1, 2, 3 을 모두 방문하게 되기 때문)
      • 이처럼 연결만 되어 있다면 정점 하나로 연결된 모든 정점들을 DFS 순회법으로 전부 방문할 수 있다.
  • now = 4 👉 DFS(4)
    • 이 호출 하나로 visited[4], visited[5] 방문
  • 이처럼 연결이 끊겨 있는 그래프를 전부 방문하기 위해 이와 같은 방법을 사용할 수 있다.
  • 한번의 DFS 순회로 연결 되어 있는 노드는 다 방문할 수 있기 때문에 if (visited[now] == false) 방문 되지 않은 정점을 검사한다는 의미는, 연결이 끊겨 있는 곳이 있을 것을 대비해서다.


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기