DFS
Depth First Search. 흔히 줄여서 DFS로 쓰입니다.
깊이 우선 탐색으로 그래프 탐색의 두 종류 중 하나 입니다. (BFS,DFS)
DFS의 특징
DFS는 일반적 검색에서는 BFS보다 느립니다.
BFS는 Queue형식으로 정답의 깊이에 따라 증가하는 방식인 반면, DFS는 전체 깊이에 따라 증가하는 방식이기 때문이죠.
다만, 순회 방식이나 이전 데이터를 저장하면서 다음 데이터를 방문하는 백트래킹에 사용됩니다.
DFS의 장단점
장점
•
현재 경로의 노드들의 정보만 기억하면 되기에 저장 공간이 비교적 적습니다.
ㄴ 여기서 비교하는 경우는 BFS의 Queue구조입니다. BFS는 구조상 다음으로 방문해야 될 곳을 Queue에 가지고 있어야됩니다. 반면, DFS는 그렇지 않죠.
•
목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수도 있습니다.
ㄴ 순차적으로 진행한 경우가 정답일 경우. DFS는 O(1) 상수 시간만에 정답을 구할 수도 있습니다.
단점
•
해가 없는 경로에 깊이 빠질 가능성이 있습니다.
ㄴ BFS와 다르게 가까운 깊이에 해가 있을 경우더라도 깊이가 아주 큰 곳을 탐색해야되는 경우 DFS는 오답일지라도 끝까지 탐색합니다.
•
얻어진 정답이 최단 경로가 된다는 보장이 없습니다.
ㄴ 정답으로 가는 해가 여러 개일 경우 그 깊이에 따라 가장 가까운 깊이가 정답인 BFS와 다르게 DFS는 가장 먼 깊이로 해를 찾을 수도 있습니다.
DFS의 탐색 방법
깊이 우선 탐색의 탐색 방법은 아래와 같습니다.
1.
루트에서 시작한다.
2.
자신의 자식 노드 중 한 곳을 방문한다.
3.
방문한 노드의 자식 노드를 방문한다.
4.
위 과정을 방문할 자식이 없는 노드까지 진행한다.
5.
만약, 정답을 찾지 못했다면, 이전 노드의 방문하지 않은 자식 노드를 방문한다.
6.
위의 과정을 반복한다.
좀 더 상새하게 설명해보겠습니다.
위 그림은 DFS를 찾는 순서를 나타낸 그림입니다.
DFS는 재귀 형식으로 구현됩니다. 현재 탐색 순서를 재귀 형식의 함수로 풀어보겠습니다.
가장 먼저, 재귀 함수 DFS에 루트 노드를 담습니다.
DFS(1)
다음으로 루트 노드 1의 자식들 2와 6을 DFS로 실행합니다.
DFS(2), DFS(6)
여기서 DFS(2)는 DFS(6)보다 먼저 실행됩니다.
DFS(2)
다음으로 노드 2의 자식들 3과 5를 DFS로 실행합니다.
DFS(3),DFS(5)
여기서 DFS(3)은 DFS(5)보다 먼저 실행됩니다.
다음으로 노드 3의 자식인 4를 DFS로 실행합니다.
DFS(4)
노드 4의 자식은 없으므로 다음으로 실행 되어야 할 DFS(5)를 실행합니다.
DFS(5)
이런 식으로 방문할 노드가 없을 때까지 혹은 정답을 찾을 때까지 DFS를 반복합니다.
아래 코드는 간단한 그래프를 DFS로 탐색한 방법입니다.
var graph = new Dictionary<int, List<int>>()
{
{ 0, new List<int> { 1, 2 } },
{ 1, new List<int> { 2, 3 } },
{ 2, new List<int> { 0, 3 } },
{ 3, new List<int> { 1, 2 } }
};
var start = 0;
var visited = new bool[4]; // 전체 노드의 크기를 4라고 합시다.
DFS(start);
void DFS(int start)
{
foreach (var node in graph[start])
{
visited[node] = true;
DFS(start);
}
}
C#
복사
