본문 바로가기

코딩/알고리즘

[초급] 백트래킹

이번에는 백트래킹에 대해 배워 보겠습니다.

 

백트래킹

백트래킹(Backtracking)모든 경우를 계산해 보는 기법을 말합니다. 비슷한 의미의 단어로 브루트 포스(Brute Force)가 있습니다. 여기서는 가장 일반적으로 사용되는, 재귀 함수를 이용한 백트래킹을 다루겠습니다.

 

백트래킹의 가장 중요한 개념은 막히면 되돌아간다라는 개념입니다.

이해를 돕기 위해 가장 대표적인 예시인 N-Queen 문제를 살펴봅시다.

 

N-Queen 문제는 $N \times N$ 크기의 체스판에 $N$개의 퀸을 서로 공격할 수 없게 배치하는 문제입니다. 체스 문제 같아 보이지만, 이 문제를 여기서 설명하는 이유는 바로 이 N-Queen 문제가 유명한 NP 문제 중 하나이기 때문입니다.

아래 배경 지식은 읽으실 분만 읽고 넘어가시면 되겠습니다. 단 뒤에서 자주 사용할 표현들에 대해서 설명하고 있으니 읽고 넘어가는 것을 추천드립니다.

 

더보기

어떤 문제가 다항 시간 안에 풀린다는 것은, 어떤 문제를 푸는 최적 알고리즘의 시간 복잡도가 변수들에 대한 다항식의 꼴로 나타난다는 것을 의미합니다.

즉 최적 알고리즘의 시간 복잡도가 $O(N^{100})$인 문제는 다항 시간 안에 풀리고, 시간 복잡도가 $O(1.1^N)$인 문제는 다항 시간 안에 풀리지 않는다고 합니다.

 

P 문제는 결정적 알고리즘(즉, 우리가 생각하는 평범한 알고리즘)을 이용했을 때 다항 시간 안에 풀리는 문제의 집합을, NP 문제는 비결정적 알고리즘(여러 가지 가능성을 동시에 고려할 수 있는 알고리즘)을 이용했을 때 다항 시간 안에 풀리는 문제의 집합을 의미합니다. 표현이 어렵다면, P 문제는 다항 시간 안에 풀리는 문제, NP 문제는 다항 시간 안에 검산 가능한 문제라고 생각하시면 됩니다.

 

P=NP 문제는 P 문제의 집합과 NP 문제의 집합이 같은 지 묻는 문제로, 아직까지 풀리지 않았습니다. 이 문제를 풀면 상금 100만 달러를 얻을 수 있지만, 아마 이 문제를 풀 정도의 사람이면 상금을 거절하지 않을까 생각합니다.

 

N-Queen 문제를 백트래킹으로 푸는 방법을 알아봅시다.

먼저 첫 번째 열에서 퀸을 놓을 수 있는 위치를 찾아봅시다. 퀸이 현재 하나도 없기 때문에, 아무 데나 퀸을 놓아도 됩니다. 첫 번째 행에 놓아 봅시다.

두 번째 열에 퀸을 놓을 수 있는 곳은 어떤 곳이 있을까요? 세 번째, 네 번째 행이 있네요. 먼저 세 번째 행에 퀸을 배치해 줍시다.

그럼, 세 번째 열에 퀸을 놓을 수 있는 곳은 어디 있나요? 놀랍게도, 퀸을 놓을 수 있는 곳은 더 이상 없습니다! 이런 경우에는, 탐색을 포기하고 전 단계로 되돌아옵니다. 이것이 바로 백트랙(Backtrack)입니다.

 

아까 세 번째 행에 퀸을 놓은 게 실수였네요. 네 번째 행에 퀸을 배치해 봅시다.

다행히도 이번에는 두 번째 행에 퀸을 배치할 수 있네요. 한 번 배치해 봅시다.

그런데, 이번에도 퀸을 배치할 수 있는 곳이 없습니다. 어떻게 된 걸까요? 바로 첫 번째 선택, 즉 퀸을 1행 1열에 놓은 선택이 잘못된 것이었습니다! 다시 처음으로 되돌아가서, 이번에는 두 번째 행에 퀸을 배치해 봅시다.

이번에는, 1~3행에 퀸을 배치할 수 없기 때문에, 유일한 선택지는 4행뿐입니다.

이번에도 유일한 선택지는 1행뿐이겠네요.

이번에는 3행에 퀸을 배치할 수 있습니다.

축하합니다! 이렇게 $N=4$일 때 퀸을 배치하는 한 가지 방법을 찾았습니다. $N=4$일 때 N-Queen 문제의 해답은 총 2가지입니다.

우리의 목표는 N이 입력으로 주어질 때, N-Queen 문제의 해답이 몇 가지인지 구하는 것입니다. [각주:1]

 

이번 예시를 통해 백트래킹이 어떤 알고리즘인지 감이 오셨나요? 맞습니다. 백트래킹은 모든 가능성을 대입해 보면서, 모순이 생겼을 경우 전 단계로 되돌아가는 알고리즘입니다.

 

백트래킹의 활용

백트래킹은 기본적으로 모든 경우를 다 해 보는 알고리즘이기 때문에, 실행 시간이 길어지는 경우가 많습니다. 따라서 입력 제한이 작은 문제에서 보통 사용하게 됩니다.

백트래킹이 특별히 어떤 유형의 문제에서 나온다고는 말하기 힘듭니다. 하지만 백트래킹은 앞에서 말했듯이, 주로 입력 제한이 작을 때 활용하게 됩니다. 항상 문제를 풀 때, 코드를 짜기 전에 시간 복잡도를 계산해 보는 습관을 기르시는 게 좋습니다.

 

연습문제

백트래킹은 연습문제를 많이 풀어보는 것으로 연습하는 것이 좋습니다. 문제별로 백트래킹을 적용하는 방법이 각기 다를 수 있기 때문입니다.

 

BOJ 16968. 차량 번호판 1 (B2)

 

백트래킹 연습하기 좋은 문제입니다. 사실 입력의 가짓수가 최대 30가지라 DB 만들어도 됩니다

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string s;
int ans = 0;

void calculate(int i, char chr){
    if(i==(int)s.size()){
        ans++;
        return;
    }
    if(s[i] == 'd'){ // 숫자 차례인 경우
        for(char x='0'; x<='9'; x++){
            if(x != chr) calculate(i+1, x);
        }
    }
    else{ // 문자 차례인 경우
        for(char x='a'; x<='z'; x++){
            if(x != chr) calculate(i+1, x);
        }
    }
}

int main(){
    cin >> s;
    calculate(0, ' '); // 공백은 숫자나 알파벳 둘 다 아닙니다
    cout << ans;
}

 

BOJ 15649. N과 M (1) (S3)

 

역시 백트래킹 연습하기 좋은 문제입니다. 다만 어떤 수를 사용했는지 체크하는 배열을 만들어야 합니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
bool chk[10];
vector<int> vec;

void backtrack(int i){
    if(i==m){ // 끝까지 왔을 때
        for(auto &x: vec) printf("%d ", x); // for(auto &x: vec) 는 vec의 원소를 차례대로 순회합니다.
        puts(""); // puts는 문자열을 출력하고 끝에 줄바꿈을 더해 줍니다. 따라서 여기서는 그냥 줄바꿈의 역할을 합니다.
        return;
    }
    for(int x=1; x<=n; x++){
        if(!chk[x]){ // x를 아직 포함하지 않았을 경우
            chk[x] = 1; // x를 포함합니다.
            vec.push_back(x); // 답 벡터에 x를 붙입니다.
            backtrack(i+1); // 다음 상태로 넘어갑니다.
            chk[x] = 0; // x 포함을 해제합니다.
            vec.pop_back(); // 답 벡터에서 x를 제거합니다.
        }
    }
}

int main(){
    cin >> n >> m;
    backtrack(0);
}

 

BOJ 9663. N-Queen (G5)

 

앞에서 설명한 문제입니다. 다만 구현이 생각보다 많이 어렵습니다.

 

더보기

각 대각선에 대해, 그 대각선 줄에 퀸을 하나라도 배치했는지를 배열에 저장해야 합니다.

대각선 번호는 $x+y$, $x-y$와 같은 식으로 붙이면 됩니다. 대각선 번호가 음수가 될 수 있으므로 적당한 수(100 정도)를 더해주면 안전합니다.

 

BOJ 1799. 비숍 (G2)

 

N-Queen보다 부가적인 처리가 조금 더 많은 문제입니다.

 

더보기

이때는 왼쪽 세로줄에서 오른쪽 세로줄로 가면서 어디에 놓을지를 판별하는 것이 아닌, 가장 왼쪽 위의 /방향 대각선에서 시작해서 한 칸 아래(또는 오른쪽)로 대각선을 이동시켜 가며 판별해야 합니다. 여러모로 처리가 까다롭지만 아이디어만 떠올리면 N-Queen과 구현 난이도가 비슷합니다.

 

 

 

  1. 앞에서 NP 문제라고 했듯이, 이 문제는 현재로서는 다항 시간 알고리즘이 없습니다. [본문으로]

'코딩 > 알고리즘' 카테고리의 다른 글

[초급] 그래프  (6) 2020.07.29
[초급] 비트마스크  (5) 2020.07.13
[초급] 백트래킹  (5) 2020.07.08
[초급] 정렬  (2) 2020.07.08
알고리즘 게시글 작성 계획  (4) 2020.07.08
  • 비키라 2020.08.15 17:37 신고

    비숍 문제의 첨언에 관하여 의문이 있습니다. P=NP 가 거짓이라면 NP 문제 중 P 문제가 아닌 것이 존재함을 의미합니다. 이 사실이 '비숍문제가 P문제에 속하지 않는다는 사실'과 동치라는 연결은 근거가 더 필요해보입니다. 분명 NP 문제 중에서도 P문제인 것이 있기 때문입니다. 더 구체적인 설명 부탁드립니다:)

    • 79brue 2020.08.15 21:08 신고

      해당 주석은 비숍 문제에 관한 것이 아닌, N-Queen 문제와 관련된 내용입니다. 이와 별개로, 해당 내용은 수정하겠습니다. 지적해 주셔서 감사합니다.

  • choiDev 2020.11.13 00:43 신고

    No.16968 차량번호판 풀이 감사히 봤습니다.
    궁금한 점이 있어서 질문드립니다.

    백트래킹은 트리구조로 데이터를 만들고 탐색하는게 기본이 아닌건가요?
    트리를 안쓰신거 같아서 여쭤봐요

    • 79brue 2020.11.13 16:17 신고

      우리가 탐색하는 상태의 구조를 그린다면 트리 구조가 되겠지만, 트리 구조로 데이터를 만들고 탐색한다기에는 무리가 있습니다. 트리는 단지 '탐색 과정'을 나타낸다고 생각하시면 됩니다.

  • choiDev 2020.11.13 16:20 신고

    답글 감사드려요~!