[Algorithm] 백트래킹(Backtracking)이란?

🚦 이번 포스팅에서는 〰️

▶️ 백트래킹(Backtracking)이란?
▶️ 백트래킹(Backtracking)문제 풀어보면서 익히기

 

📌 백트래킹(Backtracking)이란?

---

: 해를 찾는 도중 해가 아니라서 막힌다면, 되돌아가서 다시 해를 찾는 기법.

  최적화 문제와 결정 문제를 푸는 방법이 된다.

 

--> 반복문의 횟수까지 줄일 수 있음

일명 가지치기(pruning)로, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.

그러나, 문제가 N!의 경우의 수를 가질때 최악의 경우로 O(지수함수) 필요할 수 있다.

• 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
• 답이 될만한지 판단하고, 그렇지 않으면 가지치지한다.
• 주로, DFS 등 모든 경우의 수를 탐색하는 과정에서 조건문 등을 이용하여 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.
• 즉, 어떤 노드의 유망성(promising)을 검사한 후 그렇지 않다면 그 노드의 이전(부모)으로 돌아가(Backtracking) 다음 자식 노드로 진행한다. 
  
  1.  

---

 

 

 

 

📌 백트래킹(Backtracking) 문제 풀어보기

---

유명한 backtracking 문제를 풀어보면서 적용해보자.

 

백준 9663 N-Queen

 

 

크기 N*N 체스판 위 퀸 N(1<=N<15)개가 서로 공격할 수 없게 놓는 경우의 수를 출력하는 문제이다.

우선 체스에서 퀸은 상,하,좌,우,대각선 모두 제한없이 움직일 수 있다.

 

 

 

 

 

<코드>

#include <iostream>
using namespace std;
int N;
int chess[16];
int answer = 0;

bool checking(int row)
{
    for(int i=0; i<row; i++) {
        //각 행에는 하나의 queen만 있을것으로, 열을 검사
        //대각선은 비교하고 싶은 두 위치의 행번호 차이 = 열번호 차이가 같다면 대각선에 위치함.
        if(chess[row]==chess[i] || row-i == abs(chess[row]-chess[i]))
            return false;
    }
    return true;
}

void dfs(int row)
{
    if (row == N) {
        answer++;
        return;
    }
    for(int col=0; col<N; col++) {
        chess[row] = col; //(row,col)에 넣어보기

        if(checking(row)) {
            dfs(row+1); //유망하면 다음행으로 가자
        }
        //아니면 가지치기됨
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    dfs(0);

    cout << answer;

    return 0;
}

 

 

 

 

 

[Reference]

https://chanhuiseok.github.io/posts/baek-1/