백트래킹

백트래킹 

: 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

 

게임으로 비유하자면,

다음과 같은 게임에서 선택지가 나누어질 때 우리는 뭔가 하나를 정해서 가야한다. 2가지 선택지 중 첫 번째를 선택했더니 게임오버가 나왔다고 생각해보자. 그러면 되돌아와서 두 번째 선택해볼 것이고, 결론적으로 모든 경우를 다 훑어보게 된다. 즉 현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법이 바로 백트래킹이다.

백트래킹과 오목

백트래킹의 쓰임새를 하나 더 설명하자면 바둑과 오목이 있는데, 오목을 예를 살펴보자

 

우리는 파랑 돌이고 상대는 직전에 D5에 착수했다. 이 상황에서 어디에 둘 지 정해야 하는데 C5D5E5로 세로 3개가 완성된 것이 있으니 저걸 막아야 한다. 그러면 B5나 F5중 하나를 선택해야함은 자명한데 둘 중에 어디를 두는 것이 좋을까?

먼저 B5에 뒀다고 가정을 해보면 상대가 F5에 착수를 한다면 굉장히 곤란해질 것.

상대의 4-3 이 완성되었기 때문에 내가 G5에 둔다고 해도 상대가 F6에 두게 될 것이고,

내가 F6을 두면 상대는 바로 G5를 둬서 오목을 완성할 것이다. 이렇게 내가 B5에 뒀을 때 생기는 상황을 쭉 따라들어가 확인한 결과 B5에 두면 진다는 걸 알게 됐다. 

 

이런 방식이 일종의 백트래킹이다. 또한 이렇게 생긴 트리를 상태공간트리 라고 한다.

연습문제

BOJ 15649번 : N과 M (1)

 

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열

처음에는 빈 리스트로 시작한다.

여기서 첫 번째 원소를 1로 둔다. 별의 의미는 상태를 의미. 백트래킹은 상태를 넘나든다. 상태를 넘나든다는 것은 빈 리스트인 상태였다가 첫 번째 원소로 1이 쓰인 상태로 넘어가는 것과 같은 상황을 말한다. 이 때 별은 어떤 상태에 위치해있는지를 나타낸다. 지금 첫 번째 원소로 1이 쓰였으니 두 번째 원소로는 2,3,4 가 가능하다.

먼저 2를 써본다. 지금 1,2 가 채워진 상태까지 왔음을 알 수 있다.

마지막 원소로는 일단 3을 넣었다. 이렇게 모든 칸이 찼다면 수열을 완성한 것이니 출력하고 여기서는 이제 이전 상태로 되돌아가야 한다.

되돌아가기 위해 마지막 원소를 빼고 다시 마지막 원소를 채워야 하는데 3 혹은 4가 가능하다. 3은 이미 확인, 4를 넣은 상태로 이동한다.

이렇게 해서 1 2 4 를 얻어낸다. 수열을 출력했으니 돌아간다.

지금 여기서 무엇을 하는 지가 문제인데 마지막 칸으로 올 수 있는 3과 4를 다 넣어봤다. 그러니 지금 할 수 있는건 다 한 상태이고 여기서도 되돌아가면 된다.

이 다음에는 두 번째 칸에 3을 넣은 상태로 가면 된다.

현재 아직 사용하지 않은 수는 2와 4이니 먼저 마지막 칸에 2를 넣어보고 되돌아와 4를 넣으면 된다.

동작 흐름은 크게 어렵지 않다. 종이에 1부터 4까지 자연수 중에서 중복 없이 3개를 고른 수열을 쭉 나열한다고 해보면 분명 방금 한 것과 비슷한 흐름을 생각할 것이다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;  //-2^63 ~ 2^63-1
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<int, char> pic;
int INF = 1e9 + 7;
//512MB = 1.2억개 int
//if(nx<0||nx>=n||ny<0||ny>=m) continue;
/*int dz[6]={1,-1,0,0,0,0};
int dx[6]={0,0,1,-1,0,0};
int dy[6]={0,0,0,0,1,-1};*/ // 3차원 bfs
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n,m; //1부터 n까지 자연수 중에 중복 없이 m개를 고른 수열
int arr[10];
bool isused[10];
void func(int k){ //현재 k개까지 수를 택했음
    if(k==m){ //m개를 모두 택했으면
        for(int i=0;i<m;i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i=1;i<=n;i++){ //1부터 n까지의 수에 대해
        if(!isused[i]){ //아직 i가 사용되지 않았으면
          arr[k] = i; //k번째 수를 i로 정함
          isused[i] = 1; //i를 사용되었다고 표시
          func(k+1); //다음 수를 정하러 한 단계 더 들어감
          isused[i] = 0; //k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지 않았다고 명시함.
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    func(0);

    return 0;
}

arr은 수열을 담을 배열, isused는 특정 수가 쓰였는지를 true 혹은 false로 나타내는 배열이다. 앞에서 상태라는 용어를 사용했는데 n=4, m=3 에서 현재 상태가 3,2 가 채워진 상태라고 한다면 arr[0]=3, arr[1]=2 이고 1과 4는 아직 쓰이지 않았는데 2와 3은 쓰였으므로 isused[1] = false, isused[2] = true, isused[3] = true , isused[4] = false이다.

 

그 다음으로 재귀함수인데, 함수 func(k)는 현재 k까지 수를 택한 상황에서 arr[k]를 정하는 함수. 맨 처음에는 수를 한 개도 택하지 않았으니 func(0)을 호출. func(0)은 arr[0]을 정한 후에 func(1)을 호출. (arr은 0-indexed) func이 재귀 함수이니 당연히 base condition이 필요하고 k=m이 되었을 때 m개를 모두 택했으니 수열을 출력한 후 함수를 종료. 만약 k가 m이 아니라면 if문이 아닌 for문으로 들어가 1부터 n까지의 수를 차례로 확인하며 아직 쓰이지 않은 수를 찾아낸다. !isused[i] 에서 !은 논리 NOT이니까 isused[i]가 false일 때 if문이 참이 되고 arr[k] = i , isused[i] = true 로 만든 후 func(k+1) 값을 호출. 그 후 isused[i] = 0;에 도착했다는 것은 arr[k] = i로 둔 상태에서 func(k+1)에 들어갔다가 모든 과정을 끝냈다는 얘기이니 isused[i] = 0 으로 되돌려 수 i가 사용되지 않고 있음을 명시한다. arr[k]는 굳이 0과 같은 값으로 변경할 필요가 없는데 어차피 다른 값으로 덮힐 예정이기 때문.

 

N = 4, M = 2일 때 코드가 어떻게 진행되는지 살펴보자.

func(0)을 호출.

i = 1일 때, 

arr[0] = 1;

isused[1] = 1; 

---

func(1); 을 호출

i = 1일 때 isused[1]이 사용중이므로 i = 2일 때

arr[1] = 2;

isused[2] = 1;

func(2); // 1 2 출력

isused[2] = 0;

i = 3

arr[1] = 3;

isused[3] = 1;

func(2); // 1 3 출력

isused[3] = 0;

i = 4

arr[1] = 4;

isused[4] = 1;

func(2); // 1 4 출력

isused[4] = 0;

---

func(1)에서의 처리가 다 끝났으므로 func(0)에서의 처리를 마무리한다.

isused[1] = 0;

i = 2

arr[0] = 2;

isused[2] = 1;

func(1);

i = 1

arr[1] = 1;

isused[1] = 1;

func(2); // 2 1 출력

isused[1] = 0;

다음과 같은 진행 과정을 보인다.

 

호출 과정을 그림으로 살펴보자.

 

N=4, M=3 일때 func(0)을 호출할 때 어떤 일이 발생하는지 살펴보자. arr과 isused는 전역 변수. 0과 false로 초기화

이 상황에서 func(0)이 호출된다. func(0)에서 i = 1일 때 생각해보면 isused[1] 이 false이기 때문에 arr[0] = 1로 바뀌고 isused[1]= true로 바뀐 후 func(1)이 호출된다.

func(1)에서 i = 1일때 생각해보면 isused[1] = true라 넘어감. i = 2일때는 if문으로 들어가고, arr[1]=2, isused[2]=true로 바뀐 후 func(2)가 호출된다.

이 다음으로는 isused[1], isused[2]가 true이므로 i = 1, 2일 때 넘어가고 i = 3일 때는 가능하다. arr[2] = 3으로, isused[3] = true로 바뀐 후 func(3)이 호출된다. func(3)에서는 base condition에 도달했으니 지금 arr에 써져있는 대로 1, 2, 3을 출력한다.

이후 return을 만나서 돌아간다. 지금 func(3)을 들어갔다 왔으니 isused[3] = 0 을 실행할 차례. isused[3]=false가 된다.

그 다음으로 i=4 인 상황이라 arr[2] = 4,isused[4] = true가 된 후 func(3)이 호출된다. 여기까지 살펴봤는데 i는 각 상태들이 따로 가지고 있고 arr와 isused는 공통으로 사용한다는 점을 알 수 있다. 

next_permutation

C++ next_permutation을 활용해, 깔끔하게 순열과 조합을 해결할 수 있다. 코드를 살펴보자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;  //-2^63 ~ 2^63-1
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<int, char> pic;
int INF = 1e9 + 7;
//512MB = 1.2억개 int
//if(nx<0||nx>=n||ny<0||ny>=m) continue;
/*int dz[6]={1,-1,0,0,0,0};
int dx[6]={0,0,1,-1,0,0};
int dy[6]={0,0,0,0,1,-1};*/ // 3차원 bfs
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a[3]={1,2,3};
    do{
        for(int i=0;i<3;i++)
            cout << a[i] << ' ';
        cout << '\n';
    }while(next_permutation(a,a+3));
    /**
     * 출력 결과는 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
     */
    return 0;
}

next_permutation은 현재의 순열을 사전 순으로 생각했을 때의 다음 수열로 만들고 true로 반환하는 함수이다.

현재가 1 2 3이면 next_permutation을 실행한 후 next_permutation을 실행한 후 1 3 2 가 되고, 1 3 2에서 next_permutation을 실행하면 2 1 3이 된다. 만약 현재의 수열이 사전 순으로 생각했을 때 제일 마지막이어서 다음 수열이 존재하지 않는다면 false를 반환한다. 그렇기 때문에 위와 같이 do-while 문으로 작성하면 코드가 깔끔하게 떨어진다.

 

만약 중복된 수가 있다고 해도 사전 순의 결과를 잘 돌려준다.

예를 들어 1 1 2에서 시작했다면 1 2 1, 2 1 1 로 바뀌게 된다.

 

조합의 경우, 어떻게 처리하는지 살펴보자.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a[4]={0,0,1,1};
    do{
        for(int i=0;i<4;i++) {
            if (a[i] == 0)
                cout << i + 1;
        }
        cout <<'\n';
    }while(next_permutation(a,a+4));
    /**
     * 출력 결과는
12
13
14
23
24
34
     */
    return 0;
}

 

예를 들어 1 2 3 4에서 수 2개를 순서 없이 뽑는 모든 경우를 출력하는 문제를 생각해보자.

그럴 때에도 next_permutation 함수를 이용하면 되는데, 0과 1을 이용해 next_permutation을 돌리는 방법으로 해결하면 된다.

4개에서 2개를 뽑는 것이 아닌 5개에서 3개를 뽑는 문제라면 배열 a를 {0,0,0,1,1}로 두면 된다.

 

좀더 자세하게 설명하자면, {0,0,1,1} 로 next_permutation을 돌리면 다음과 같은 순열이 나온다.

/**
* 
0 0 1 1 
0 1 0 1 
0 1 1 0 
1 0 0 1 
1 0 1 0 
1 1 0 0
*/

위에서부터 a[i]가 0일때 i+1을 출력하면 조합을 구할 수 있다. 첫번째 줄은 1 2, 두번째 줄은 1 3...

이런 식으로 조합을 구할 수 있다.

 

출처 : 바킹독님 블로그 https://blog.encrypted.gg/945