DFS (Depth-First Search)

1. Depth-First Search (깊이우선검색)

뿌리노드(root)가 되는 노드(node)를 먼저 방문한 뒤, 

그 노드의 모든 후손노드(descendant)들을 차례로 (보통 왼쪽에서 오른쪽으로) 방문한다. (= preorder tree traversal)

- DFS 알고리즘

2. Back Tracking (되추적)

어떤 노드의 유망성(promising, 답이 나올 가능성이 있는 노드)을 점검한 후, 

유망하지 않다고 판정되면 그 노드의 부모노드로 돌아가서(backtrack) 

다음 후손노드에 대한 검색을 계속 진행하는 과정이다.

- 되추적 알고리즘의 개념

  되추적 알고리즘은 깊이우선검색(DFS)을 실시하는데,

  유망하지 않은 노드들은 검색을 하지 않으며 유망한 노드에 대해서만 그 노드의 자식노드를 검색한다.

- 진행 절차

  ㄱ. 깊이우선검색(DFS)을 실시한다.

  ㄴ. 각 노드가 유망한지를 점검한다.

  ㄷ. 만일 그 노드가 유망하지 않으면, 그 노드의 부모노드로 돌아가서 검색을 계속한다.

- Backtracking 알고리즘

3. DFS 예

 - 4-Queens Problem

 

   4개의 Queen을 서로 상대방을 위협하지 않도록 4 × 4 chess판에 위치시키는 문제이다.

  서로 상대방을 위협하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야 한다.

         

 

 

 - Graph Coloring

  m-coloring: 지도에 m가지 색으로 색칠하는 문제이다.

  m개의 색을 가지고, 인접한 지역이 같은 색이 되지 않도록 지도에 색칠하는 문제이다.