[바킹독의 알고리즘] 0x0C강 - 백트래킹

0x00 알고리즘 설명

여러 선택지마다 달라지는 결과 예시들

 

오목처럼 한 가지 수의 대한 여러가지 가능성

 

자료구조로 위 트리는 상태공간트리라고 부른다.

 

 

 

 

 

 

 

 

0x01 연습 문제 1 - N과 M

BOJ 15649번: N과 M(1)

15649번: N과 M (1)

 

 

 

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

int 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] << ' '; // 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);
}

 

 

 

 

 

 

 

 

 

0x01 연습 문제 2 - N-Queen

BOJ 9663번: N-Queen

9663번: N-Queen

 

 

퀸과 퀸끼리 부딫이는 여부 체크 3가지

1. y좌표(열)가 일치하는가
2. x+y(윗방향 대각선) 값이 일치하는가
3. x-y(아랫방향 대각선) +n-1(인덱스를 음수로 보내지 않기 위한 장치) 값이 일치하는가

 

y좌표(열)가 일치하는가

 

x+y(윗방향 대각선) 값이 일치하는가

 

x-y(아랫방향 대각선) +n-1(인덱스를 음수로 보내지 않기 위한 장치) 값이 일치하는가

 

 

 

 

#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;
}

 

 

 

 

 

 

 

 

 

 

 

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

BOJ 1182번: 부분수열의 합

1182번: 부분수열의 합

 

 

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

int n, s;
int cnt = 0;
int arr[40];
void func(int cur, int total){
    if(cur == n){
        if(total == s) cnt++;
        return;
    }
    func(cur+1, total);
    func(cur+1, total+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;
}

 

 

 

 

 

 

 

 

0x04 STL next_permutation

 나중에 코딩테스트 문제들을 풀다보면 순열과 조합을 가지고 코딩 노가다가 빡세게 들어가는 것들을 보게 된다. 당장 N과 M 시리즈도 그런 유형이다.

 

이런 문제들을 백트래킹으로 해결할 수 있지만 아무래도 백트래킹은 실수할 수 있는 여지가 있고 코드도 길어진다. 그런데 이 next_permutation 함수만 있다면 아주 깔끔하게 순열과 조합을 해결할 수 있다.

 

 

 

 

위 사용 예시를 보면 1 2 3을 가지고 만들 수 있는 모든 순열을 위와 같이 쉽게 구할 수 있다.

 

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

현재가 1 2 3이면 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로 바뀌게 된다.

 

 

 

 

조합이 필요하다면 어떻게 해야할지 고민해보자. 예를 들어 1 2 3 4에서 수 2개를 순서 없이 뽑는 모든 경우를 출력하는 문제와 같은 상황이다. 그럴 때에도 이 함수를 이용하면 되는데 오른쪽의 코드를 확인해보겠다.

 

바로 0과 1을 이용해 next_permutation을 돌리는 방법으로 해결하면 된다. 4개에서 2개를 뽑는게 아니라 5개에서 3개를 뽑는 문제라면 배열 a를 {0, 0, 0, 1, 1}로 두면 되겠다. 이와 같이 next_permutation을 쓰면 순열과 조합이 필요할 때 아주 정확하고 또 타이핑을 아끼면서 구현을 해낼 수 있다.