17. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이란?

 

 

 

"깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)"

 

 

개발을 하다보면 연결된 데이터를 따라가며 원하는 대상 찾기 / 경로 찾기 / 영역 확장 같은 일을 해야 하는 순간이 많다.

 

Unity에서도 Hierarchy를 훑어 컴포넌트를 찾거나, 그리드 맵에서 가까운 칸부터 퍼져 나가거나,

연결된 구역을 판별하는 상황에서 결국 탐색이 등장한다.

 

 

이때 가장 대표적인 두 가지가 DFS(Depth-First Search)와 BFS(Breadth-First Search)이다.

 

 

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

 

 

1) DFS와 BFS란?

DFS(깊이 우선 탐색)

한 갈래를 끝까지 깊게 들어갔다가, 막히면 되돌아오며 탐색한다.

 

BFS(너비 우선 탐색)

시작점에서 가까운 것(거리/레벨)부터 넓게 퍼지며 탐색한다.

 

 

 

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

 

 

 

2) '방문 순서'는 왜 다를까?

 

 

DFS는 '깊이', BFS는 '거리/레벨'을 기준으로 움직이기 때문에 방문 순서가 달라진다.
(추가로, 그래프/트리 모두 이웃(자식) 리스트의 순서에 따라 방문 순서가 달라질 수 있다.)

 

 

 

 

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

 

 

 

3) 그래프에서 visited가 중요한 이유

 

트리에는 보통 사이클이 없어서 단순하지만, 그래프는 사이클(cycle)이 생길 수 있다.
visited가 없으면 이미 갔던 노드로 되돌아가면서 무한 반복이 발생할 수 있다.

 

visited(방문 체크)가 필요한 이유

(보통 큐/스택에 넣는 순간에 visited 표시를 해두는 편이 중복 삽입을 줄이고 안정적임)

 

 

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

 

 

 

4) DFS / BFS 예시 코드

 

(A) 그래프 예시 코드 (인접 리스트)

using System.Collections.Generic;

Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>
{
    { 0, new List<int> { 1, 2 } },			//	   1
    { 1, new List<int> { 0, 2, 3 } },                   //        / \
    { 2, new List<int> { 0, 1 } },			//	 0---2
    { 3, new List<int> { 1, 4 } },			//	  \
    { 4, new List<int> { 3 } },				//	   3---4
};

 

 

 

(B) DFS (재귀)

using System.Collections.Generic;

public static class GraphSearch
{
    public static List<int> DFS_Recursive(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int>();
        var order = new List<int>();

        void Dfs(int v)
        {
            if (visited.Contains(v)) return;

            visited.Add(v);
            order.Add(v);

            foreach (var next in graph[v])
                Dfs(next);
        }

        Dfs(start);
        return order;
    }
}

 

 

 

(C) DFS (스택)

using System.Collections.Generic;

public static class GraphSearch
{
    public static List<int> DFS_Stack(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int>();
        var order = new List<int>();
        var stack = new Stack<int>();

        stack.Push(start);

        while (stack.Count > 0)
        {
            int v = stack.Pop();
            if (visited.Contains(v)) continue;

            visited.Add(v);
            order.Add(v);

            var neighbors = graph[v];
            for (int i = neighbors.Count - 1; i >= 0; i--)
                stack.Push(neighbors[i]);
        }

        return order;
    }
}

 

 

 

(D) BFS (큐)

using System.Collections.Generic;

public static class GraphSearch
{
    public static List<int> BFS_Queue(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int>();
        var order = new List<int>();
        var q = new Queue<int>();

        visited.Add(start);
        q.Enqueue(start);

        while (q.Count > 0)
        {
            int v = q.Dequeue();
            order.Add(v);

            foreach (var next in graph[v])
            {
                if (visited.Contains(next)) continue;
                visited.Add(next);
                q.Enqueue(next);
            }
        }

        return order;
    }
}

 

 

 

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

 

 

5) 시간 복잡도

DFS / BFS = O(V + E)
(인접 리스트 기준) 

V = 정점 수, E = 간선 수

(인접 행렬로 표현하면 이웃 확인 비용이 커져서 O(V²) 형태로 체감될 수 있음)

 

 

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

 

 

 

6) Unity에서는 언제 DFS/BFS를 쓸까?

DFS가 어울릴 때

 

깊게 파고드는 구조에 사용

(Hierarchy 탐색, 백트래킹, 경우의 수 탐색)

 

BFS가 어울릴 때

 

가까운 것부터 / 최단 칸 수 / 영역 확장에 사용

(그리드 최단 이동, Flood Fill 등)

 

 

 

 

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

 

 

 

7) 오늘의 한줄 요약

 

『 DFS/BFS는 트리·그래프에서 연결을 따라가며 탐색하는 방법이며, 

DFS는 깊게, BFS는 가까운 것부터 방문한다. 』