개요

💡 DFS에 대해서 알아보자.

C++로 깊이 우선 탐색(DFS)을 알아 보고 구현해보자.

참고 자료

본론

---

DFS(깊이 우선 탐색)

개념

DFS는 Depth-First Search의 약자로 '깊이 우선 탐색'을 의미합니다.

순환 알고리즘 중 하나로, 자료구조에서 루트 노드 혹은 임의의 노드에서 시작해서
다음 분기로 넘어가기 전에 해당 분기에 대한 완전 탐색 기법 중 하나입니다.

주로, 재귀함수 또는 Stack로 구현합니다.

특징

시간 복잡도

DFS은 정점 노드의 개수를 N, 간선의 개수를 E라고 할 때,

인접 행렬에서는 O(N²)의,
인접 리스트에서는 O(N+E)의 시간 복잡도를 가집니다.

장점

현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적습니다.

목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있습니다.

단점

노드에 대한 방문 여부를 체크하지 않으면 무한 루프에 빠질 수 있습니다.

이는 각 노드에 대한 방문 여부를 검사하여 해결하고,
지정된 깊이까지만 탐색하는 조기 종료가 사용되기도 합니다.

또한 얻어진 해가 최단 경로가 된다는 보장이 없습니다.

구현

노드와 간선으로 이루어진 2차원 벡터 A가 있다고 하겠습니다.

노드 번호	인접 노드
1	2, 3, 4
2	1, 4
3	1, 4
4	1, 2, 3

그리고 각 노드의 방문 여부를 체크할 bool 벡터 visited도 만들어 주겠습니다.

static vector<bool> visited(N+1,false);

재귀 함수를 사용하여 DFS를 구현해보겠습니다.

1번 노드를 기준으로 진행하겠습니다.

void DFS(int node);

int main()
{
	DFS(1);
}

void DFS(int node)
{
	visited[node] = true;
    
    for (int i : A[node])
    {
    	if (!visited[i])
        {
        	visited[i] = true;
            DFS(i);
        }
    }
}

기본적인 DFS 알고리즘은 위와 같습니다.

이제 미로 찾기, 단절점 찾기, 단절선 찾기, 위상 정렬 등의 문제에 맞게 각 조건을 추가로 DFS 함수 내부에 구현해주면 됩니다.

---

마무리

이상으로 DFS의 개념과 기본 알고리즘 구현에 대해서 정리하였습니다.

추후 DFS 알고리즘의 코딩 테스트를 풀어 보도록 하겠습니다.