[실전 알고리즘] 0x0C강 - 백트래킹

1. 알고리즘 설명

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

상태공간트리 - 백트래킹의 모든 후보군의 상태를 나타내는 트리.

 

---

2. 연습 문제 1 - N과 M

BOJ 15649번: N과 M (1)

15649번: N과 M (1)

8중 for문으로도 구현 가능하지만 백트레킹을 이용하면 더 좋다.

 

#include <bits/stdc++.h>
#define MAX 10
using namespace std;
int n,m;
int arr[MAX];
bool isused[MAX];

void func(int k){  // 현재 k개까지 수 선택.
    if (k == m){  // m개 모두 선택.
        for (int i = 0;i<m;i++){
            cout << arr[i] << ' '; // arr에 기록해둔 수 출력.
        }
        cout << '\n';
        return;
    }
    for (int i = 1;i<=n;i++){  // 1부터 n까지
        if(!isused[i]){  // 아직 i가 사용되지 않았으면
            arr[k] = i;  // k번째 수를 i로 
            isused[i] = true;  // i 사용 표시
            func(k+1);  // 다음 수 정하러 들어감.
            isused[i] = false;  // k번째 수를 i로 정한 모든 경우 확인 완료했으니 이제 i 사용 안 함 표시.
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    func(0);

    return 0;
}

n과 m은 입력으로 주어진 값이고 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까지 수를 차례로 확인하며 아직 쓰이지 않은 수를 찾아낸다.

---

3. 연습 문제 2 - N-Queen

BOJ 9663번: N-Queen

9663번: N-Queen

int cnt = 0;
// cur번째 행에 말 배치
void func(int cur){
  if(cur == n){
    cnt++;
    return;
  }
  ...
}

func(0)을 호출해 0번째 행에 퀸을 배치하고 func(0)은 func(1)을 호출하고, 이렇게 진행하다가 func(n)이 호출되면 퀸 n개를 놓는데 성공했다는 의미이니 cnt를 1 증가시킨다.

 

그럼 특정 좌표에 퀸을 둘 수 있는지를 어떻게 판단할까?

행, 열, 대각선에 대해 확인한다.

대각선 판단은 x+y가 같으면 같은 좌측 하단, 우측 상단을 잇는 대각선이고 x-y가 같으면 좌측 상단과 우측 하단을 잇는 대각선이다. 

 

지금까지 놓은 놓은 퀸의 목록을 외부 변수로 가지고 있다가 func 함수 안에서 퀸을 놓을 때 각 퀸과 대각선 혹은 열에서 만나는 것이 있는지를 확인하면 된다.

 

그런데 여기 더 좋은 방법이 있다.

 

isused가 true인지만 확인하는 것이다. isused 없이는 지금 수를 쓸 수 있는지 최대 M-1개의 수를 확인해야 하기에 그 과정에서 O(M)이 필요한데 isused를 쓰면 O(1)에 바로 알 수 있다는 장점이 있다. 이 문제에서는 각 대각선과 열의 점유 상태를 나타낼 isused 변수를 두면 시간을 절약할 수 있다.

 

isused1은 열에 대응되는 값으로, (x, y)에 퀸이 있으면 isused1[y]를 true로 만들면 된다. isused2는 좌측 하단과 우측 상단을 연결하는 대각선이고 (x, y)에 퀸이 있으면 isused2[x+y]를 true로 만들면 된다. 마지막은 좌측 상단과 우측 하단을 연결하는 대각선이고 (x, y)에 퀸이 있으면 isused3[x-y+n-1]을 true로 만들면 된다.

 

+) n-1은 인덱스를 음수로 보내지 않게 하기 위해서 처리한 것이다.

 

만약 (cur, i)에 퀸을 둘 수 있다면 isused1[i], isused2[cur+i], isused[cur-i+n-1]을 true로 변경한 후 func(cur+1)을 호출한다. 

 

+) A1에 퀸을 놓으면 바로 B1, B2에 퀸을 놓는 경우는 해볼 필요가 없어지는 것과 같은 상황을 백트래킹에서 가지치기라고 부르는데 가지치기가 빈번하면 백트래킹의 시간복잡도를 가늠하기가 많이 힘들다. 따라서 문제를 보고 시간복잡도가 가늠이 잘 안가는데 N이 많이 작아 백트래킹으로 푸는 문제일 것 같다는 생각이 들면 직접 구현한 뒤 가장 시간이 오래 걸릴만한 케이스를 직접 돌려봐서 시간 초과가 나는지 안나는지를 보면 된다. 만약 시간이 애매하면 최대한 최적화할 수 있는 것들을 찾아서 고치고 제출을 하면 된다. 시간을 로컬에서 측정할 때에는 반드시 Release 모드로 실행을 해야 하고 보통은 서버가 로컬보다 빠르다는 점도 기억하시면 좋다.

 

 

---

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

BOJ 1182번: 부분수열의 합

1182번: 부분수열의 합

원소가 n개인 집합에서 부분집합의 갯수 -  2^n

 

문제에서의 표현은 수열과 부분수열이지만 부분집합을 고르는 것과 동일한 상황이니 공집합은 빼고 2^n-1개의 모든 부분수열에 대해 합이 S와 일치하는지를 확인하면 된다. 

#include <bits/stdc++.h>
using namespace std;
int n,s,cnt;
int arr[50];

void func(int cur, int sum){
    if (cur == n){
        if (sum == s){
            cnt++;
        }
        return ;
    }
    func(cur + 1, sum);
    func(cur + 1, sum + arr[cur]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> s;
    for (int i = 0;i<n;i++){
        cin >> arr[i];
    }
    func(0, 0);
    if (s == 0){
        cnt--; // 공집합 제외
    }
    cout << cnt;

    return 0;
}

 

---

5. STL next_permutation

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

0과 1을 이용해 next_permutation을 돌리는 방법으로 조합도 해결가능하다.

 

레퍼런스

http://www.cplusplus.com/reference/algorithm/next_permutation/

next_permutation - C++ Reference

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));

/*
123
132
213
231
312
321
*/

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

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

---

참고자료

[실전 알고리즘] 0x0C강 - 백트래킹

[실전 알고리즘] 0x0C강 - 백트래킹