[0x0C] 백트래킹

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

 

상태공간트리라는 개념을 이용한다.

재귀 호출 전후로 선택지를 true와 false로 변경해 주는걸 잊으면 안된다.

 

가지치기가 빈번하게 일어날수록 시간 복잡도를 계산하기 매우 어렵다.

재귀로 구현되는 경우 n값이 크지 않아야 한다.

 

원소가 n개인 집합에서 부분집합의 개수는 공집합을 포함하여 2ⁿ개이다.

 

n값이크지 않은 경우에 완전탐색, 구현할때 자주 써먹을 수 있을 것 같다.

 

백트래킹의 전형적인 코드

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

 

출처 : 바킹독

 

연습 문제

 

15649: N과 M (1)

#include <iostream>

using namespace std;

int nums[10];
bool isUsed[10];

int n, m;

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < m; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!isUsed[i])
		{
			nums[k] = i;
			isUsed[i] = true;
			backtracking(k + 1);
			isUsed[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

 

백트래킹 입문 문제

코드를 잘 뜯어먹어보면 어느정도 이해가 간다.

 

9663: N-Queen

#include <iostream>

using namespace std;

int answer;
bool isExRow[16];
bool isExDiagonal1[32];
bool isExDiagonal2[32];

int n;

void backtracking(int k)
{
	if (k == n)
	{
		answer++;
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		if (isExRow[i] || isExDiagonal1[i + k] || isExDiagonal2[i - k + n - 1])
		{
			continue;
		}
		isExRow[i] = true;
		isExDiagonal1[i + k] = true;
		isExDiagonal2[i - k + n - 1] = true;
		
		backtracking(k + 1);

		isExRow[i] = false;
		isExDiagonal1[i + k] = false;
		isExDiagonal2[i - k + n - 1] = false;
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	backtracking(0);

	cout << answer;

	return 0;
}

 

퀸의 공격 경로를 확인하는게 가장 어려운 부분. 조금 변칙적이지만 전형적인 백트래킹 문제.

행에 놓는게 기본이니 행의 검사는 안해도 됨.

좌하단에서 우상단의 경로는 x+y, 좌상단에서 우하단의 경로는 x-y(인데 index가 음수로 가지 않기위해 n-1을 더해준다)

 

1182: 부분수열의 합

#include <iostream>

using namespace std;

int answer = 0;
int nums[20];

int n, s;

void backtracking(int k, int tot)
{
	if (k == n)
	{
		if (tot == s) // 상태공간트리 끝에 도달
		{
			answer++;
		}
		return;
	}
	backtracking(k + 1, tot); // 합계에서 수를 선택하지 않음
	backtracking(k + 1, tot + nums[k]); // 합계에서 수를 선택해서 합산
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> s;
	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	backtracking(0, 0);

	if (s == 0)
	{
		answer--; // s가 0일때 공집합 제거
	}

	cout << answer;

	return 0;
}

 

더하거나, 더하지 않거나 두개의 경우가 있다는 것을 알아야 한다.

중복이 허용되지 않는 순열

 

기본 문제

 

15650: N과 M (2)

#include <iostream>

using namespace std;

int n, m;
bool isused[20];
int nums[20];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	// 같은수는 고르면 안돼서 1을 더함
	int st = (k != 0) ? nums[k - 1] + 1 : 1;

	for (int i = st; i <= n; ++i)
	{
		if (!isused[i])
		{
			isused[i] = true;
			nums[k] = i;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

 

st와 같은 개념을 떠올리긴 했는데 구현이 떠오르지 않아서 풀이를 봤음

중복이 허용되지 않는 순열, 비내림차순

 

15651: N과 M (3)

#include <iostream>

using namespace std;

int n, m;
int nums[20];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; ++i)
	{
		nums[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

 

중복이 허용되는 순열의 경우 isused가 필요가 없다

 

15652: N과 M (4)

#include <iostream>

using namespace std;

int n, m;
int nums[20];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? nums[k - 1] : 1;

	for (int i = st; i <= n; ++i)
	{
		nums[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	backtracking(0);

	return 0;
}

 

중복이 허용되는 순열, 비내림차순

 

15654: N과 M (5)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int nums[10];
vector<int> arr;
bool isused[10001];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		if (!isused[arr[i]])
		{
			nums[k] = arr[i];
			isused[arr[i]] = true;
			backtracking(k + 1);
			isused[arr[i]] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;
		arr.push_back(t);
	}

	sort(arr.begin(), arr.end());

	backtracking(0);

	return 0;
}

 

1~8이 아닌 임의의 수에 대한 순열. 기본적인 백트래킹과 똑같은 방식. vector와 정렬을 이용해 해결

** isused를 1만까지 늘릴필요 없이 인덱스를 보관하면 됨. vector도 안써도 됨

중복을 허용하지 않는 순열, 임의의 수

 

15655: N과 M (6)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx[10];
int nums[10];
bool isused[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[idx[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] + 1 : 0;

	for (int i = st; i < n; ++i)
	{
		if (!isused[i])
		{
			idx[k] = i;
			isused[i] = true;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

 

임의의 수를 이용하는 경우 직접적인 수가 아닌 해당 수가 저장된 배열의 인덱스를 보관해서 해야 한다.

중복을 허용하지 않는 순열, 임의의 수, 비내림차순

 

15656: N과 M (7)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[idx[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		idx[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

 

중복이 허용되는 순열, 임의의 수

 

15657: N과 M (8)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << nums[idx[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] : 0;

	for (int i = st; i < n; ++i)
	{
		idx[k] = i;
		backtracking(k + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

 

중복을 허용하는 순열, 임의의 수, 비내림차순

 

15663: N과 M (9)

#include <iostream>
#include <algorithm>

using namespace std;

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

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int tmp = 0;
	for (int i = 0; i < n; ++i)
	{
		if (!isused[i] && tmp != nums[i])
		{
			arr[k] = nums[i];
			tmp = arr[k];
			isused[i] = true;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

 

이번에는 isused에 배열의 인덱스 사용여부를 저장하지만 arr에는 인덱스가 아닌 숫자를 직접 저장한다.

tmp에 최근 숫자를 저장함으로써 79 79와 같은 같은 수열이 두번 나오지 않게 방지함.

이 문제가 가장 이해하기 어려운거같음.

중복이 허용되지 않는 순열, 중복된 숫자가 포함된 임의의 수

 

15664: N과 M (10)

#include <iostream>
#include <algorithm>

using namespace std;

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

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k-1] + 1 : 0;
	int tmp = 0;

	for (int i = st; i < n; ++i)
	{
		if (!isused[i] && tmp != nums[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			tmp = arr[k];
			isused[i] = true;
			backtracking(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

idx, arr, isused 모두 사용한다.

중복을 허용하지 않는 순열, 중복된 숫자가 포함된 임의의 수, 비내림차순

 

15665: M과 N (11)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10];
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int tmp = 0;

	for (int i = 0; i < n; ++i)
	{
		if (tmp != nums[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			tmp = arr[k];
			backtracking(k + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

 

중복이 허용되는 조합. isused 미사용

 

15666: N과 M (12)

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10];
int idx[10];
int nums[10];

void backtracking(int k)
{
	if (k == m)
	{
		for (int i = 0; i < k; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] : 0;
	int tmp = 0;

	for (int i = st; i < n; ++i)
	{
		if (tmp != nums[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			tmp = arr[k];
			backtracking(k + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> nums[i];
	}

	sort(nums, nums + n);

	backtracking(0);

	return 0;
}

 

N과 M 정리

 

- 1부터 N까지 오름차순인 경우의 백트래킹

중복이 허용되지 않는 순열 : isused와 고른 숫자를 보관할 arr 두개만 있으면 된다

 

중복이 허용되지 않는 순열 및 오름차순 : 앞서 저장된 숫자보다 큰곳부터 시작하는 st가 추가로 필요하다. 0인경우 1, 0이 아닌경우 바로 앞에 저장된 숫자에 +1

 

중복이 허용되는 순열 : isused와 st를 사용하지 않는다

 

중복이 허용되는 순열 및 오름차순 : isused를 사용하지 않고 st만 추가로 필요하다

 

 

 

- 임의의 수에 대한 경우의 백트래킹

* 입력을 다 받고 오름차순으로 정렬해야한다 *

 

중복이 허용되지 않는 순열 : 고른 숫자의 인덱스를 보관할 idxarr가 추가로 필요하다. isused는 사용중인 인덱스를 true/false 하도록 한다.

 

중복이 허용되지 않는 순열 및 오름차순 : st를 사용하며, 숫자가 아닌 인덱스로 판별한다. 0인경우 0, 0이 아닌경우 바로 앞에 저장된 인덱스에 +1

 

중복이 허용되는 순열 : isused와 st를 사용하지 않는다

 

중복이 허용되는 순열 및 오름차순 : isused를 사용하지 않고 st만 추가로 필요하다

 

 

 

- 중복된 숫자가 포함된 임의의 수에 대한 경우의 백트래킹

* 입력을 다 받고 오름차순으로 정렬해야한다 *

 

중복이 허용되지 않는 순열 : 고른 숫자를 보관할 arr가 필요하다. idx는 사용하지 않는다. 현재 선택된 값을 임시로 보관하여 비교할 tmp가 추가로 필요하다. isused 판별할 때 tmp != nums[i]도 추가로 판별해야 한다

 

중복이 허용되지 않는 순열 및 오름차순 : 값 저장은 여전히 하며, idx도 추가로 필요하다. idx를 토대로 st도 사용한다

 

중복이 허용되는 순열 : isused와 st를 사용하지 않는다

 

중복이 허용되는 순열 및 오름차순 : isused를 사용하지 않고 st만 추가로 필요하다

 

 

6603: 로또

// N과 M을 통해 익힌 코드로 풀이한 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[15];
int idx[15];
int nums[15];
bool isused[15];

void backtracking(int k, int& n)
{
	if (k == 6)
	{
		for (int i = 0; i < 6; ++i)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	int st = (k != 0) ? idx[k - 1] : 0;

	for (int i = st; i < n; ++i)
	{
		if (!isused[i])
		{
			idx[k] = i;
			arr[k] = nums[i];
			isused[i] = true;
			backtracking(k + 1, n);
			isused[i] = false;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	while (true)
	{
		int n;
		cin >> n;
		
		if (!n)
		{
			return 0;
		}

		for (int i = 0; i < n; ++i)
		{
			cin >> nums[i];
		}

		sort(nums, nums + n);

		backtracking(0, n);

		cout << '\n';
	}

	return 0;
}

  

// next_permutation을 이용해 풀이한 코드

#include <iostream>
#include <algorithm>

using namespace std;

int nums[15];
int arr[15];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	while (true)
	{
		int n;
		cin >> n;
		
		if (!n)
		{
			return 0;
		}

		for (int i = 0; i < n; ++i)
		{
			cin >> nums[i];
			if (i >= 6)
			{
				arr[i] = 1;
			}
		}

		sort(nums, nums + n);

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

		cout << '\n';
	}

	return 0;
}