굳건하게

문제 : https://www.acmicpc.net/problem/9663

[알고리즘풀이]

큰 틀은 백트레킹 기법을 이용해서 Row마다 가능한 모든 자리에 Queen을 세워보는 것이다.

vector<int> v 에는 지금까지 Queen을 세운 자리가 저장되어있다.

ex) v[0] = 1 이라면 0번째 row, 1번째 column에 Queen을 세웠다.

i번 째 row에 Queen을 세우는 방법은 그동안 0 ~ (i - 1)번 째 row에 세워둔 Queen들과 같은 열이 아니고, 대각선 상에 위치하지 않으면 된다. 따라서 같은 열이 아닌지, 오른쪽 아래로 내려가는 대각선 상에 있지 않은지, 왼쪽 아래로 내려가는 대각선 상에 있지 않은지 Check해서 모두 통과한다면 그 자리에는 Queen을 세울 수 있다.

#include<iostream>
#include<vector>

using namespace std;

int n, c;

void bt(int, vector<int>);

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		vector<int> v; // v에는 열을 넣는다.
		v.push_back(i);
		bt(1,v);
		v.pop_back();
	}
	cout << c;
}

void bt(int row, vector<int> v) {
	if (row == n ) {
		c++;
		return;
	}
	for (int i = 0; i < n; i++) {
		// 같은열을 체크하자.
		bool check1 = false;
		for (int j = 0; j < row; j++)
			if (i == v[j]) {
				check1 = true;
				break;
			}
		if (check1)
			continue;
		// 오른쪽 대각선을 체크하자.
		bool check2 = false;
		for (int j = 0; j < row; j++) {
			if (i == v[j] + (row + 1) - (j + 1)) {
				check2 = true;
				break;
			}
		}
		if (check2)
			continue;
		// 왼쪽 대각선을 체크하자.
		bool check3 = false;
		for (int j = 0; j < row; j++) {
			if (i == v[j] - (row + 1) + (j + 1)) {
				check3 = true;
				break;
			}
		}
		if (check3)
			continue;
        // 다 통과하면 Queen을 세워보자.
		v.push_back(i);
		bt(row + 1, v);
		v.pop_back();
	}
}

문제 : https://www.acmicpc.net/problem/15652

[알고리즘풀이]

중복은 허용되지만, 오름차순으로 뽑아야하므로 가장 마지막에 담긴 원소를 넘겨주며 백트레킹 기법을 구현한다.

#include<iostream>
#include<vector>

using namespace std;

int m, n;

void bt(int, int, vector<int>);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		vector<int> v;
		v.push_back(i);
		bt(1, i, v);
		v.pop_back();
	}
}

void bt(int count, int start, vector<int> v) {
	if (count == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int k = start; k <= n; k++) {
		v.push_back(k);
		bt(count + 1, k, v);
		v.pop_back();
	}
}

문제 : https://www.acmicpc.net/problem/15651

[알고리즘풀이]

중복이 허용되고, 오름차순도 지킬 필요가 없으므로 그냥 조건 없는 백트레킹을 구현한다.

#include<iostream>
#include<vector>

using namespace std;

int m, n;

void bt(int, vector<int>);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		vector<int> v;
		v.push_back(i);
		bt(1, v);
		v.pop_back();
	}
}

void bt(int count, vector<int> v) {
	if (count == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int k = 1; k <= n; k++) {
		v.push_back(k);
		bt(count + 1, v);
		v.pop_back();
	}
}

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

[알고리즘풀이]

중복을 체크해줘야 되므로 visited 배열을 활용하고, 오름차순으로 진행해야 되므로, 가장 마지막에 담긴 값을 이용해서 백트레킹을 설계한다.

#include<iostream>
#include<vector>

using namespace std;

bool visited[9];

int m, n;

void bt(int, int);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n - m + 1; i++) {
		visited[i] = true;
		bt(1,i);
		visited[i] = false;
	}
}

void bt(int count, int start) {
	if (count == m) {
		for (int k = 1; k <= n; k++)
			if (visited[k])
				cout << k << ' ';
		cout << '\n';
		return;
	}
	for (int k = start; k <= n; k++) {
		if(visited[k] == false){
			visited[k] = true;
			bt(count + 1, k);
			visited[k] = false;
		}
	}

}