DFS(Depth First Search - 깊이 우선 탐색)

⊙ 학습 목표

코드스니펫

 

DFS란?

DFS(Depth First Search)는 깊이 우선 탐색이라는 의미로, 트리나 그래프를 최대한 깊이 들어가서 탐색하는 방법이다. 즉, 제일 바닥을 찍는 것을 목표로 하는 방식이다.

 

그림에서 보이는 것처럼 루트, 시작 노드에서 시작해 가장 멀리 있는 정점을 방문, 더 방문할 정점이 없거나 원하는 노드가 아니라면 다시 돌아가서 탐색한다.

 

사용처

1. 모든 경우의 수(혹은 모든 경로)를 찾는 경우
2. 퍼즐을 푸는 문제인 경우
3. 미로 문제를 해결하는 경우

 

---

 

구현 방법

DFS는 스택, 재귀로 구현한다.

void DFS(int node){
	// 해당 노드에 대한 방문 처리
    visit[node] = true;

	// 해당 노드에서 원하는 일(출력)을 함
    printf("%d ", node);

	// 이곳과 연결된 노드들 중 방문하지 않은 노드 탐색하기
    for(int i = 1; i <= n; i++){
        if(!visit[i] && edge[node][i])
            DFS(i);   // 재귀 호출로 구현
    }
}

 

---

 

백 트래킹

트리에서 탐색하는 과정 중 '이 경로는 무조건 정답이 나올 수 없다' 하는 경우가 있다. 예를 들어 돈은 10000원 있는데 10만원을 써야 한다던지 등등... 이럴 경우 더 이상 탐색이 의미가 없어진다. 다시 루트 노드로 돌아가 다른 경로를 탐색해야 한다.

 

다만 DFS와 백트래킹은 항상 함께하는 것이 아니니 문제의 특성을 잘 고려해 트리의 끝까지 가야 한다면 DFS만을 사용해야 한다.

 

 

---

 

배운 내용 정리

• 내용