[백트래킹]

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘으로, 대표적으로 오목 같은 경우 놓을 수 있는 모든 수에 대한 상태공간트리를 만들어 해결하는 것과 같은 알고리즘이다.

---

연습문제

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

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

void func(int k)
{
    if(k==m)
    {
        for(int i = 0;i<m;i++)
        {
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    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)
{
    cin >> n >> m;
    func(0);
    
}

• func(int k) 함수는 arr[k]에 들어갈 수를 결정하는 함수이다. 만약 k==m이 되어서 꽉찬다면 배열을 출력하고, 그게 아니라면, n이하의 수 중에서 arr에 안들어간 i번째 수를 찾고 arr에 넣고, func(k+1)을 호출한다. 그 뒤 다시 arr에서 뺀 다.

---

연습문제 2

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

int n;
bool isused1[15];
bool isused2[30];
bool isused3[30];
int cnt = 0;

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

• 우선, 한 행에는 하나의 말만 올 수 있다. 따라서 모든 행에 하나씩의 말이 들어가야한다.
• 또한 하나의 행에 말을 둔다면, 그 말이 놓인 열과 좌우대각선 위치에는 말이 놓일 수 없다.
• 이것을 해결하기위해 열, 좌대각, 우대각 방문체크 배열을 만들어 백트랙킹을 돌린다.
• isused1 배열은 말이 놓인 열에 방문이 불가능 하다는 것을 체크해둔다.
• isused2 배열은 말이 놓인 우상향좌하향 대각선에 방문이 불가능하다는 것을 체크해둔다.
• isused3 배열은 말이 놓인 좌상향우하향 대각선에 방문이 불가능하다는 것을 체크해둔다.

---

연습문제 3

// boj 1182
#include <iostream>    
using namespace std;
int n,m;
int arr[21];
int ans;
void recursive(int k,int sum)
{
    if(k==n)
    {
        if(sum==m)
            ans++;
        return;
    }
    recursive(k+1,sum);
    recursive(k+1,sum+arr[k]);
    
}

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

• 여러 차례 시간초과가 발생해서 결국 실패한 문제이다.
• 방문배열을 만드는 시도를 해보았으나 결국은 재귀함수내의 반복문 때문에 시간복잡도를 못맞춰 실패하였다.
• 이를 해결하기위해 방문 배열을 두기보다는, 다음 원소를 합하는 경우, 합하지 않는 경우를 모두 호출하여 분기시켰다....

---

next_permutation

• 순열과 조합 을 활용하는 데에 알고리즘이다.
• 해당원소로 만들 수 있는 다음 순열이 존재한다면 true 를 리턴하고, 원소의 배치를 다음 순열로 만든다.

순열을 이용하는 경우

int arr[3]={1,2,3};
do{
	for(int i =0;i<3;i++)
    cout << arr[i] << ' ';
cout << '\n';
}while(next_permutation(arr,arr+3));

조합을 이용하는 경우

int arr[5] = {0,0,0,1,1};
do{
	for(int i = 0;i<5;i++)
    	if(arr[i]==0)
    		cout << i+1;
cout << '\n';
}while(next_permutation(arr,arr+5);