[C++/코테] 백트래킹: 백준 15649, 9663, 1182

백트래킹

• 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
• 재귀를 활용하여 구현하므로, 함수의 기본 틀은 base condition - i일 때 조건 확인 - 조건 변경 - i+1에 대해 함수 실행 - 조건 변경 해제 와 같은 식으로 진행된다. 백트래킹의 전형적인 구조라고 볼 수 있으므로 아래 연습 문제들을 참고하여 익혀두자.

연습문제

1. N과 M

백준 15649번 N과 M(1): https://www.acmicpc.net/problem/15649

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

int n, m;
int arr[10];
bool isused[10];

void func(int k) // 현재까지 k개의 수 선택했을 때, arr를 정하는 함수
{
    if (k == m) // k개를 모두 택했으면
    {
        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] = 1; // i를 사용되었다고 표시
            func(k + 1);   // 다음 수를 정하러 한 단계 더 들어감
            isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지 않았다고 명시함
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0); // 0개의 숫자 선택
}

2. N-Queen

백준 9663번 N-Queen: https://www.acmicpc.net/problem/9663

✔️퀸은 체스판에서 상하좌우, 대각선에 있을 때 서로 공격할 수 있다.

✔️ 1 ≤ N < 15 이기 때문에 백트래킹으로 해결할 수 있다.

 

함수의 기본 틀

int cnt = 0;
void func(int cur){
    if(cur == n){
        cnt++;
        return;
    }
 ...
 }

지난 문제에서 순회하지 않고 값을 알기 위해서는 isused와 같이 배열과 인덱스를 사용해서 $O(1)$이 걸려 값을 얻을 수 있었다. 백트래킹은 결국 많은 경우의 수를 순회하고 조건을 따지게 되므로 배열을 잘 활용하면 좋을 것 같다.

해당 문제에서 필요한 조건은 상하좌우, 대각선의 위치이므로 활용할 수 있는 배열은 다음과 같다.

• isused1 - 상하. y값으로 비교 가능
• isused2 - 좌측 하단과 우측 상단 연결 대각선(↗). x+y값으로 비교 가능
• isused3 - 좌측 상단과 우측 하단 연결 대각선(↘). x-y+n-1값으로 비교 가능

C++ 답안 출처

// http://boj.kr/4e7fe4509a3842598592fe4ed79900c0
#include <bits/stdc++.h>
using namespace std;
bool isused1[40]; // column을 차지하고 있는지
bool isused2[40]; // / 방향 대각선을 차지하고 있는지
bool isused3[40]; // \ 방향 대각선을 차지하고 있는지

int cnt = 0;
int n;
void func(int cur) { // cur번째 row에 말을 배치할 예정임
  if (cur == n) { // N개를 놓는데 성공했다면
    cnt++;
    return;
  }
  for (int i = 0; i < n; i++) { // (cur, i)에 퀸을 놓을 예정
    if (isused1[i] || isused2[i+cur] || isused3[cur-i+n-1]) // column이나 대각선 중에 문제가 있다면
      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. 부분수열의 합

백준 1182 부분 수열의 합: https://www.acmicpc.net/problem/1182

✔️원소가 n개인 집합에서, 부분 집합의 갯수는 $2^n$이다. ( 공집합 포함)

✔️수열을 순회하며 각 원소를 더할 지, 더하지 않을 지 2가지로 나눠 모든 경우의 수를 알아낼 수 있다.

C++ 답안 참고

// http://boj.kr/792d9af025724ce2912c77e8d56793d1
#include <bits/stdc++.h>
using namespace std;

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

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> s;
  for(int i = 0; i < n; i++)
    cin >> arr[i];
  func(0, 0);
  if(s == 0) cnt--;
  cout << cnt;
}

 

---

출처: https://blog.encrypted.gg/945

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