[바킹독 실전 알고리즘 0x0C] 백트래킹

알고리즘 설명

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

백트래킹은 상당한 구현력을 필요로 하고, 실수하기도 쉽다. 따라서 많은 시간을 할애해 재귀의 개념을 익히고, 연습을 해야한다. 처음엔 어렵게 느껴지겠지만, 생각보다 응용의 폭이 넓지 않아 BFS와 비슷하게 기본적인 코드 뼈대를 익혀두면 훨씬 더 수월하게 풀이할 수 있다.

 

연습문제1 - N과 M

BOJ 15649번)

백트래킹의 기본 코드는 대략적으로 익혀두는 것이 좋다.

#include <bits/stdc++.h>
using namespace std;

//전역 변수
int n, m; //입력 받는 값들
int arr[10]; //수열을 담을 배열
bool isused[10];  //특정 수가 쓰였는지를 나타내는 배열(상태를 저장하는 배열)

//재귀 함수
//k까지의 수를 택한 상황에서 arr[k]를 택하는 함수
void func(int k){

	//base condition
	if(k == m){ //수열의 원소를 모두 택했으니 출력하고 종료하면 된다.
    	for(int i=0; i<m; i++)
        	cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    
    //base condition이 아니라면
    for(int i=1; i<=n; i++){
    	if(!isused[i]){ //아직 사용하지 않은 원소일 때
        	arr[k] = i;
            isused[i] = 1;
            func(k+1);
            isused[i] = 0;
            }
        }
    }
int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0);
}

 

연습문제2 - N-Queen

BOJ 9663번)

NxN 체스판에 퀸 N개를 서로 공격하지 못하는 위치에 놓는 경우의 수를 구하는 문제이다. 퀸은 체스판 위에서 상하좌우와 대각선으로 공격할 수 있는 기물이다. N=4 일때, 가능한 체스판의 배치는 다음과 같다:

이 문제의 경우, N<=14 인 조건이 있으므로 백트래킹으로 해결할 수 있다. 백트래킹으로 구현하는 절차는 그렇게 복잡하지 않다. 

먼저, 해답이 되는 함수의 기본 틀은 다음과 같다: 

func(0)을 호출해 0번째 행에 퀸을 배치한 후, func(0)은 func(1)을 호출해 1번째 행에 퀸을 배치하게 된다. 이렇게 재귀적으로 함수를 호출하다가 func(n)을 호출하게 되면, n개의 퀸을 모두 호출했다는 의미이므로 cnt를 1 증가시킨다. (cnt는 가능한 배치의 수를 저장하는 변수이다.)

int cnt = 0;

//cur번째 행에 말을 배치할 예정임
void func(int cur){
	if(cur == n){
    	cnt++;
        return;
    }
    ...특정 좌표에 퀸을 둘 수 있는지를 어떻게 판단할 것인지 check하는 코드...
}

그렇다면, 특정 좌표에 퀸을 둘 수 있는지는 어떻게 판단하면 좋을까?

한 행에 두 개의 퀸을 놓을 수 없다는 사실은 자명하므로 이 경우를 제외하고,

i)같은 열에 퀸이 있는 경우

ii)기울기가 +1인 대각선 위에 있는 경우

iii)기울기가 -1인 하나의 대각선 위에 있는 경우

세 가지를 고려해야 한다.

 

i) 경우는 두 퀸의 y좌표가 같은지를 통해 확인할 수 있다. 다음과 같이 n=4인 경우, y좌표는 0,1,2,3으로 이루어질 것이고, 해당 y좌표를 가지는 퀸이 있다면 상태를 저장하는 배열인 isused1[i] 의 값을 1로 설정하면 된다.

ii) 경우는 x+y값이 같은 좌표가 있는지 확인함을 통해 알 수 있다. 고등학교 수학에서 기울기가 -1인 일차함수(x+y=k) 위에 있는 모든 점은 x값과 y값의 합이 일정하다는 것을 배웠었는데, 이를 떠올려보면 쉽게 이해할 수 있을 것이다.

iii) 경우는 x+y+n-1값이 같은 좌표가 있는지 확인함을 통해 알 수 있다. ii)에서 소개한 고등수학 내용과 비슷한 원리로 기울기가 +1인 직선 위의 모든 점은 x-y값이 동일하다. 여기서 n-1값을 붙여준 이유는 이 값을 isused3[i] 배열의 인덱스로 사용해야하는데, 음수 값을 가지면 안되기 때문이다.

func(cur)에서는 위의 세 가지 경우를 확인하고 (cur,0), (cur,1), ...,(cur,n-1)에 퀸을 둘 수 있는지를 확인하게 된다. 이 때 퀸을 둘 수 있는지는 isused1, isused2, isused3의 값을 통해 판단할 수 있다. 만약 점(cur, i)에 퀸을 둘 수 있다면 isused1[i], isused2[cur+i], isused3[cur-i+n-1] 을 true로 변경한 후, func(cur+1)을 호출한다. 

 

코드를 전부 구현하면 다음과 같다:

C++ code)

#include <bits/stdc++.h>
using namespace std;
bool isused1[40];
bool isused2[40];
bool isused3[40];

int cnt = 0;
int n;
void func(int cur){
	if(cur == n){
    	return;
    }
    for(int i=0;i<n;i++){
    	if(isused1[i] || isused2[i+cur] || isused3[cur-i+n-1])
        	continue;
        isused1[i] = 1;
        isused2[i+cur] = 1;
        isused3[cur-i+n-1] = 1;
        func(cur+1);
        isused1[i] = 0;
        isused2[i+cur] = 0;
        isused3[cur-i+n-1] = 0;
        }
    }
int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    func(0);
    cout << cnt;
}

 

연습문제3 - 부분수열의 합

원소가 n인 집합의 부분집합의 개수는 2^n이다. 집합의 각 원소는 어떤 부분집합의 원소가 될 수도, 안 될수도 있기 때문에 그렇다. 이 배경지식을 알고 있다면 문제를 풀기 수월하다.

 

STL next_permutation

순열과 조합 문제를 해결할 때 유용한 STL 함수이다. 

레퍼런스: http://www.cplusplus.com/reference/algorithm/next_permutation

https://cplusplus.com/reference/algorithm/next_permutation/

사용법은 다음과 같다:

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을 가지로 만들 수 있는 모든 순열을 이렇게 쉽게 구할 수 있다. next_permutation은 현재 수열을 사전 순으로 생각했을 때, 다음 수열을 만들고 true를 반환하는 함수이다. 현재 수열이 1 2 3 이라면 next_permutation을 실행한 후 1 3 2 를 반환하고, 이 상태에서 또 next_permutation을 실행하면 수열은 2 1 3이 된다. 만약 현재 수열이 사전 순으로 생각했을 때 가장 마지막이어서 출력할 다음 수열이 없다면 false를 반환한다. 따라서 위와 같이 do-while문을 사용하는 것이 적합하다.

 

만약 이 함수를 가지고 조합 문제를 풀고 싶다면 어떻게 해야 할까?

 0과 1을 이용해 next_permutation을 돌리면 된다. 서로 다른 4개의 수 중 2개를 뽑고 싶다면 int a[4] = {0,0,1,1}로, 서로 다른 5개의 수 중 3개를 뽑고 싶다면 int a[5] = {0,0,0,1,1}로 설정하면 된다.

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
*/