[알고리즘] DFS(Depth First Search) 깊이 우선 탐색이란

DFS(Depth First Search)란?

• 한 경로를 끝까지 탐색한 후, 이전 경로로 돌아가서 다른 경로를 탐색하는 방법이다.
• DFS에서 사용하는 알고리즘은 백트래킹(backtracking) 알고리즘이다. 백트래킹이란 해를 찾아가는 도중 지금 가는 경로가 해가 아니라면 왔던 경로로 되돌아가는 것을 의미한다. 즉, 트리의 마지막 노드에 도달했을 경우 이전 노드로 되돌아가서 새로운 경로를 찾는 것을 의미한다.
• 재귀 함수와 스택을 이용하여 구현한다. 재귀를 이용할 경우 종료 조건을 명시해서 무한 반복에 빠지지 않게 해야 한다.딱 두 가지만 생각하면 된다.
• DFS 탐색 과정

1. 한 경로를 끝까지 탐색한다.
2. 마지막 노드에 도달했다면 이전 노드로 돌아가서(backtracking) 탐색하지 않은 노드가 있는지 확인한다.
   • 탐색하지 않은 노드가 있다면 그 노드를 방문하여 새로운 경로를 끝까지 탐색한 후 같은 과정을 반복한다.(->1번)
   • 탐색하지 않는 노드가 없다면 다시 이전 노드로 돌아가서 탐색하지 않는 노드가 있는지 확인한다.(->2번)

DFS 구현 방법

순환 호출(재귀)

1. 현재 노드를 방문했다면 함수를 종료하고 방문하지 않았다면 방문했다고 처리한다.
2. 현재 노드의 모든 인접 노드에 대해 재귀적으로 탐색을 진행한다

스택

1. 시작 노드를 스택에 추가한다.
2. 스택에서 노드를 하나 꺼내고, 그 노드가 방문되지 않았다면 방문 처리를 한다.
3. 현재 노드의 모든 인접 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 스택이 비어 있을 때까지 1~3번 과정을 반복한다.

DFS 주요 유형

미로 탈출 문제(백트래킹 대표 문제)

2차원 공간에서 고양이의 좌표는 (0, 0), 츄르의 좌표는 5, 5)이다. 이때 고양이가 튜르를 먹기 위해 미로를 이동하는 경우이다.
이때 DFS 백트래킹을 이용해 길을 찾는 방법은 4단계로 이루어져 있다.

1. 상, 하, 좌, 우를 보고 이동할 수 있는 곳을 찾는다.
2. 이동할 수 있는 공간으로 이동한다.
   • 상, 하, 좌, 우 중 우선순위는 미리 정한다.
3. 1번과 2번을 반복하다가 더 이상 갈 수 있는 공간이 없을 경우 되돌아간다.
   • 재귀를 이용하여 뒤로 가거나 스택을 이용하여 미리 저장된 index로 돌아간다.
4. 1번, 2번, 3번을 반복하며 탈출구를 찾는다.

• ex. '상'이 '우'보다 우선순위일 경우 상황을 보자

'상'이 우선순위이기 때문에 잘못된 경로를 끝까지 탐색한 후 되돌아와서 해의 경로인 오른쪽 경로로 이동한다.

// 변수 선언
int NUM_DIRECTIONS = 4;

static int DIRECTION_OFFSETS[NUM_DIRECTIONS][2] = {
    {0, -1},        // 0 (상)
    {1, 0},            // 1 (우)
    {0, 1},            // 2 (하)
    {-1, 0}            // 3 (좌)
};

struct MapPositionType
{
    int x;                
    int y;                
    int direction;
} MapPosition;

enum PosStatus { NOT_VISIT = 0, WALL = 1 , VISIT = 2  };

// 재귀 함수
int findPath(int maze[HEIGHT][WIDTH], MapPosition pos, LinkedStack *pStack)
{
    MapPosition nextPos;
    int nextX;
    int nextY;

    if (!pStack)
        return (ERROR);
        // 현재 위치가 미로의 범위를 벗어나는 지 확인
    if (pos.x < 0 || pos.y < 0 || pos.x >= WIDTH || pos.y >= HEIGHT)
        return (FALSE);
        // 현재 위치가 벽이거나 이미 방문한 곳인지 확인
    else if (maze[pos.y][pos.x] == WALL || maze[pos.y][pos.x] == VISIT)
        return (FALSE);
        // 도착 지점에 도달한 경우
    else if (maze[pos.y][pos.x] == END)
    {
        pushLS(pStack, pos);
        return (TRUE);
    }
        // 백트래킹을 통한 탐색 반복
        else
    {
        pushLS(pStack, pos); // 현재 위치를 스택에 저장
        maze[pos.y][pos.x] = VISIT; // 현재 위치를 2로 변경
        while (pos.direction < NUM_DIRECTIONS)
        {
            // 다음 좌표 설정
            nextX = pos.x + DIRECTION_OFFSETS[pos.direction][0];
            nextY = pos.y + DIRECTION_OFFSETS[pos.direction][1];
            nextPos.x = nextX;
            nextPos.y = nextY;
            nextPos.direction = 0;
            if (findPath(maze, nextPos, pStack))
                return (TRUE);
            pos.direction += 1;
        }
        // 길을 찾지 못하면 스택에서 현재 위치 제거
        popLS(pStack);
        return (FALSE);
    }
}

연결 요소 찾기

DFS의 한계

DFS의 단점은 크게 2가지가 있다.

1. 연산 횟수 기하급수적 증가

DFS는 가능한 모든 경우의 수를 탐색한다.
때문에 미로의 크기가 커지면 커질 수록 연산 횟수는 기하급수적으로 커진다.

• 예를 들어 갈 수 있는 길이 3가지 모두 존재하는 갈림길이 3개 있다고 가정해보자.

1		1	1	1	1	1
1		1		1		1
1	1	1	1	1	1	1	1	1
		1		1		1		1
		1	1	1	1	1		👑

3가지 가능한 경우가 존재하는 갈림길이 3개 존재한다.
따라서, 갈림길에서 선택할 수 있는 경우의 수는 3^3가지이다.
그런데 만약 갈림길이 1000개라면 경우의 수는 3^1000으로 기하급수적으로 늘어난다.

2. 최단 거리 보장 X

상, 하, 좌, 우의 우선순위를 미리 정해서 탐색한다.
이때 우선순위를 어떻게 정하느냐에 따라서 거리가 달라지기 때문에 항상 최단거리를 보장하지 못한다.

• 예시
  아래 경로가 있다고 가정하자

1(strat)		1	1	1
1		1		1
1		1	1	1
1	1	1		1
		1	1	1(finish)

만약 탐색 순서가 '상 -> 우 -> 하 -> 좌'라면 다음과 같이 탐색한다.

1🏃‍♂️		1	1	1
2🏃‍♂️		1		1
3🏃‍♂️		7🏃‍♂️	8🏃‍♂️	9🏃‍♂️
4🏃‍♂️	5🏃‍♂️	6🏃‍♂️		10🏃‍♂️
		1	1	11🏃‍♂️

탐색 순서가 '하 -> 우 -> 상 -> 좌'라면 다음과 같이 탐색한다.

1🏃‍♂️		1	1	1
2🏃‍♂️		1		1
3🏃‍♂️		1	1	1
4🏃‍♂️	5🏃‍♂️	6🏃‍♂️		1
		7🏃‍♂️	8🏃‍♂️	9🏃‍♂️

이렇게 순서에 따라 경로가 달라진다.
따라서, 최단 거리를 찾기 위해서는 DFS보다 BFS를 사용한다.

출처

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://80000coding.oopy.io/51503941-ff71-4cd4-a4cc-ec8a68eddbb7