백트래킹 2

백트래킹 문제를 풀다가 중복제거, 오름차순 정렬 등을 좀 더 간단하게 하고 싶어서 정리한 내용입니다.

 

기존에 정리한 글

https://gbleem.tistory.com/124

백트래킹

 

1. 순열 구하기

---

기본 형식의 백트래킹 코드를 돌리면 순열을 구할 수 있다. 

• 1 ~ n까지의 숫자 중에서 m개를 뽑는 경우
• 중복은 제거

void Choose(int cur)
{
	if (cur == m)
	{
		for (const int& a : ans)
		{
			cout << a << " ";
		}
		cout << "\n";

		return;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!isused[i])
		{
			ans.push_back(i);
			isused[i] = 1;
			Choose(cur + 1);
			ans.pop_back();
			isused[i] = 0;
		}
	}
}

 

4 2를 input으로 넣었을 때 아래와 같은 결과가 나온다.

 

 

2. 조합 구하기

---

순열을 구하는 코드에서 시작점을 뜻하는 start라는 매개변수를 추가하여 보면 아래와 같이 구현할 수 있다.

void Choose(int cur, int start)
{
	if (cur == m)
	{
		for (const int& a : ans)
		{
			cout << a << " ";
		}
		cout << "\n";

		return;
	}

	for (int i = start; i <= n; ++i)
	{
        ans.push_back(i);
        Choose(cur + 1, i + 1);
        ans.pop_back();
	}
}

 

이 코드의 실행 결과는 아래와 같다.

 

 

3. 실습

---

조합을 구하기

https://www.acmicpc.net/problem/15650

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int isused[10];
vector<int> ans;

void Choose(int cur, int start)
{
	if (cur == m)
	{
		for (const int& a : ans)
		{
			cout << a << " ";
		}
		cout << "\n";

		return;
	}

	for (int i = start; i <= n; ++i)
	{
        ans.push_back(i);
        Choose(cur + 1, i + 1);
        ans.pop_back();
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	Choose(0, 1);
}

 

오름차순 조합 구하기

https://www.acmicpc.net/problem/15655

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int board[10];
vector<int> ans;

void Choose(int cur, int start)
{
	if (cur == m)
	{
		for (const int& a : ans)
			cout << a << " ";
		cout << "\n";
		return;
	}

	//index
	for (int i = start; i < n; ++i)
	{
		ans.push_back(board[i]);
		Choose(cur + 1, i + 1);
		ans.pop_back();
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> board[i];
	}
	sort(board, board + n);
	Choose(0,0);

}

 

중복이 가능한 오름차순 조합

https://www.acmicpc.net/problem/15666

• 내 처음 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n, m;
int board[10];
vector<int> ans;
set<vector<int>> s;

void Choose(int cur)
{
	if (cur == m)
	{		
		s.insert(ans);
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		if (ans.empty() || (!ans.empty() && ans.back() <= board[i]))
		{
			ans.push_back(board[i]);
			Choose(cur + 1);
			ans.pop_back();
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> board[i];

	sort(board, board + n);

	Choose(0);
	for (const auto si : s)
	{
		for (const auto a : si)
			cout << a << " ";
		cout << "\n";
	}
}

• 다른 아이디어
  • 생각해볼만 하지만, 잘 이해는 안된다.
  • 중복은 그냥 set으로 처리하는게 나을지도

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
int board[10];
int ans[10];

void Choose(int cur, int start)
{
	if (cur == m)
	{
		for (int i = 0; i < m; ++i)
			cout << ans[i] << " ";
		cout << "\n";
		return;
	}
	int temp = -1;
	for (int i = start; i < n; ++i)
	{
		if (board[i] != temp)
		{		
			ans[cur] = board[i];
			temp = ans[cur];
			Choose(cur + 1, i);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> board[i];

	sort(board, board + n);

	Choose(0, 0);
}