[자료구조] DFS(깊이 우선 탐색)

 

DFS(Depth First Search)

• 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

 

 

DFS 과정

1. 방문해야 하는 칸을 스택에 넣는다. 방문했다는 표시를 bool 배열에 넣는다.
2. 스택에서 원소를 꺼내고 해당 칸에서 상하좌우로 인접한 칸에 대해 3번 과정을 진행한다.
3. 처음 해당 칸을 방문했다면 방문했다는 표시를 bool 배열에 남기고 해당 칸을 큐에 삽입한다.
   해당 칸을 이전에 방문했다면 아무것도 하지 않는다. 
4. 스택이 빌 땍까지 2번 과정을 반복한다. 

 

 

시간 복잡도

방문해야 하는 칸은 스택에 1번씩 들어간다. 최악의 경우 방문해야 하는 칸이 N개라면 시간 복잡도는 O(N)이다. 

 

 

코드

namespace DFS
{
    internal class DFS구현
    {
        static int[,] board = new int[,]
        {
            {1,1,1,0,1,0,0,0,0,0},
            {1,0,0,0,1,0,0,0,0,0},
            {1,1,1,0,1,0,0,0,0,0},
            {1,1,0,0,1,0,0,0,0,0},
            {0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0} 
        };
        static bool[,] visit = new bool[512,512];

        const int N = 7;
        const int M = 10;

        static int[] dx = { 1, 0, -1, 0 };
        static int[] dy = { 0, 1, 0, -1 };

        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        static void Main(string[] args)
        {
            Stack<(int X, int Y)> stack = new Stack<(int X, int Y)>();
            visit[0, 0] = true;
            stack.Push((0, 0));

            while(stack.Count > 0)
            {
                (int X, int Y) cur = stack.Peek();
                stack.Pop();

                sw.WriteLine($"({cur.X}, {cur.Y}) -> ");

                for(int dir = 0; dir < 4; dir++)
                {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if (visit[nx, ny] || board[nx, ny] != 1) continue;

                    visit[nx, ny] = true;
                    stack.Push((nx, ny));
                }
            }

            sw.Close();
        }
    }
}

 

 

BFS VS DFS

BFS는 거리 순서대로 방문하고, DFS는 한 방향으로 막힐 때까지 방문한다. 

BFS는 큐 자료구조를 사용하고, DFS는 스택 자료구조를 사용한다. 

BFS는 먼저 들어간 것이 먼저 빠져나오고 (First In First Out), DFS는 나중에 들어간 것이 먼저 빠져나온다. (Last In First Out)

 

BFS는 먼저 들어간 것 그러니까 최근 것이 먼저 빠져나오므로 BFS는 최단거리 측정에 적합하다. 

DFS는 나중에 들어간 것이 먼저 빠져나오므로 DFS는 최단거리 측정이 힘들다. (한 방향을 우선적으로 탐색하기 때문)

 

 

Flood Fill(영역 방문)은 BFS, DFS 모두 사용할 수 있다. 

그러나 최단 거리 측정은 BFS만 가능하다. 

 

그래프, 트리 자료구조를 배울 때 DFS가 필요하다. 

지금은 간단하게 DFS는 "스택을 사용해서 다차원 배열을 순회 처리하는 알고리즘" 정도로만 알고있자. 

 

	BFS	DFS
탐색 방식	거리 순서대로 탐색	한 방향으로 막힐 때까지 탐색
사용하는 자료구조	큐(Queue) - FIFO(First In First Out)	스택(Stack) - LIFO(Last In First Out)
최단거리 측정	적합	부적합
Flood Fill (영역 방문)	적합	적합