Algorithm&DataStructure - Backtracking

1. Backtracking

- 모든 경우의 수를 고려하는 트리탐색 알고리즘이다.

- 탐색중 현재 경로가 유망하지 않다면 가지치키를 할 수 있다.

- 유망하지 않다 = 더 이상 탐색할 필요가 없다.

2. 백준 15649번

- 1부터 n 까지의 자연수 중 서로 다른 m개를 골라 줄세우는 경우들을 구한다. (nPm)

- m에 따라서 경우의 수 tree가 만들어진다.

- 이 트리에 대해서 깊이 우선의 탐색을 수행하는데 조건에 따라 탐색을 중지할 수 있다.

- 이미 m개를 골랐다면 더 이상 깊이 트리를 탐색할 필요가 없으니 종료 조건에서 가지치를 하는 것이다.

void backtracking(int count = 0)
{
  if(count == m)
  {
    for(int i =0; i<m; i++)
    {
      cout<<list[i]<<" ";
    }
    cout<<'\n';
    return ;
  }
  

  for(int i =1; i<=n; i++)
  {
    if(!check[i-1])
    {
      list[count]=i;
      check[i-1]=true;
      backtracking(count+1);
      check[i-1]=false;
    }
  }
  
}

- 코드를 순서대로 보면 맨 위에 종료 조건이 있다. 유망하지 않다면 이 깊이로 탐색은 더 의미가 없기 때문에 연속된 재귀 호출들을 모두 종료하도록 한다. 

 

- 경로탐색에서 노드를 방문했는지 아닌지 여부를 저장하는 visited 배열은 반드시 필요하다.

 

- check를 backtracking 전후로 true/false 해주는 이유는 다음과 같다. 

- 1 2 _ _ 의 경우를 다 파악했다면 13 _ _ 의 탐색이 수행될 것이다. 근데 2를 계속 방문했다고 체크해두면 1 3 2 4 등의 경로는 탐색하지 못할 것이다. 

- 이게 dfs와의 차이이다. dfs는 모든 노드를 방문하면 끝나지만 backtracking은 모든 경우의수(경로)를 찾는 것이기 때문에 방문 여부를 탐색 후 복구 해주어야 한다.

- 같은 이유로 방문여부와 더불어 count도 원래 값으로 바꾸어 줘야 한다. 그래서 count+1 처럼 값으로 매개변수를 전달한다.

3. 백준 9663번

- N-QUEEN 문제라고 한다.

- 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 구하라.

void backtracking(int x=0)
  {
    if(x==n)
    {
      cases++;
      return;
    }
    
    for(int j =0; j<n; j++)
      if(check(x,j))
      {
        list.push_back(j);
        backtracking(x+1);
        list.pop_back();
      }
  }

- 종료조건은 n개의 퀸을 성공적으로 다 두어서 x 가 n이 되었을 때이다.

 

- 각 가로 줄에 퀸을 하나씩만 둘수 있기 때문에 j에 대해서만 반복을 수행한다.

- (x,j)에 퀸을 둘 수 있는지 보드를 체크한다. 

- 퀸을 둘 수 있다면 보드에 퀸을 놓고 다음 깊이로 내려가서 트리 탐색을 수행한다.

- (x,j)에 퀸을 두었을때 탐색 가능한 경로들을 다 확인했으니 이제는 (x,j)에 둔 퀸을 치워줘야 한다.

 

- 즉 백트래킹에서는 딱 세가지만 주목하면 된다.

1. 재귀를 통해 트리를 탐색

2. 종료 조건에 따라 가지치기

3. 경로를 찾는 문제이기 때문에 방문 여부, 종료 조건 등을 재귀 호출 전후로 복구해주어야 한다.