[Algorithm] 완전 탐색 - 백트래킹(Backtracking), 깊이 우선 탐색(DFS. Depth-first search)

모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가, 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다.
- 나무 위키 -

 

백트래킹(Backtracking)

비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때,

더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정을 말한다.

백트래킹 과정의 단순화

• 일반적으로 최적화 문제를 해결할 때 사용하는 방법이다.
• 문제를 비선형으로 구조화한 다음, 가능한 모든 상태를 깊이 우선으로 탐색해가며 해를 구성해 나간다.
• 이 과정에서 더 이상 탐색을 진행할 수 없으면 백트래킹하여 다시 다른 상태를 조사해 나간다.
• 모든 가능한 상태를 다 조사하며 이를 백트래킹 기법이라 한다.

 

문제해결 방법

 ① 주어진 문제를 비선형 구조로 구조화한다.

 ② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

 ③ 구성된 해를 정리한다.

 

예제 및 알고리즘

주어진 3 x 3 행렬에서 개의 원소를 서로 행과 열이 중복되지 않도록 선택하는 게임이 있다.
여기서 얻을 수 있는 최소 점수는 얼마인가?

행과 열이 중복되지 않아야 하므로 일단 각 행에서 1개 이상의 값은 얻을 수 없다.

그리고 서로 열도 중복하지 않아야 하므로 위 문제는 다음과 같이 구조화할 수 있다.

구조화

위 그림의 탐색 구조는 1행 1열의 1을 선택했을 때의 탐색 구조의 일부이다.

행과 열이 중복되지 않아야 하므로 {2}를 선택할 수 없다.
따라서 깊이 우선으로 구할 수 있는 첫 번째 해는 아래 그림과 같다.

처음으로 구한 해

처음으로 구한 해 1-4-5를 탐색하여 구한 수는 10이다.

문제의 조건에 따랏 1행 1열, 2행 2열을 선택했기 때문에 3행에서는 1열과 2열을 선택할 수 없다.

10이 최종적인 해인지 아닌지 현태 상태로는 확정할 수 없다.
따라서 백트리킹으로 가능한 모든 해를 구해야만 최종적으로 해를 구할 수 있다.

백트래킹

1로 백트래킹을 한 다음 7값을 가지는 노드로 진행해 새로운 해를 구할 수 있다.

백트래킹을 계속 진행해 구할 수 있는 모든 해를 나열하면 다음과 같다.

{1, 7, 3} = 11, {5, 2, 5} = 12, {5, 4, 5} = 14, {3, 2, 3} = 8, {3, 4, 5} = 12

구할 수 있는 최소 점수는 3, 2, 3을 선택해 나올 수 있는 8점이 정답이 된다.

int m[3][3] = {
   {1, 5, 3},
   {2, 5, 7},
   {5, 3, 5}
};

int col_check[3] = {false, false, false};

min_sol = INT_MAX;

void backtracking(int row, int score)
{
   if(row == 4)
      if(score < min_sol)
         min_sol = score;
      return;
   for(i = 1; i <= 3; i = i + 1)
      if(col_check[i] == false)
         col_check[i] = true;
         backtracking(row + 1, score + m[row][i]);
         col_check[i] = false;
   return;
}

main()
{
   backtracking(1, 0);
   print min_sol on the screen;
}

 

깊이 우선 탐색(DFS, Depth-first search)

• 완전탐색 방법 중 하나
• 탐색 트리의 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색해 나가는 기법 (backtracking 과정이 존재)

  

깊이 우선 탐색

장점

• 단지 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다.
  • 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 탐색하는 방법도 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.
  • 목표에 이른 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내므로, 이때 얻은 해가 최적이 아닐 수 있다.