백트래킹(2) 순열, 조합, N Castle C++

개요

1. 중복 순열

중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려한다, 중복 조합)

별다른 판별조건 없이 모든 수를 도출해 주면 된다.

1 1 2
1 2 1
2 1 1

 

2. 순열

서로 다른 N개 중에서 R개를  선택하는 경우의 수(순서를 고려한다, 중복인 경우는 선택하지 않는다.)

DAT를 활용하여 이미 선택한 경우에는 선택하지 않도록(방문 여부 체크) 판별조건을 추가해 준다.

1 2 3
1 3 2
2 3 1

 

3. 중복 조합

중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려하지 않는다.)

중복이 가능하다 = 방문 처리를 하지 않는다.

조합을 위해 현재 뽑는 순서가 2번째 이상일 경우 이전에 뽑았던 수보다 작을경우 선택하지 않는다. 라는 판별 조건을 추가해 준다.

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

 

예제

1. 중복 조합

3개의 주사위에서 R개의 숫자의 조합을 추출하는 경우, 중복을 허용하고 순서를 고려하지 않는다.

코드

#include <iostream>

using namespace std;

int n;
int DAT[7];

void bt(int index) {
	if (index == 3) {
		for (int i = 0; i < 3; i++) {
			cout << DAT[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i < 7; i++) {
		if (index > 0 && DAT[index - 1] > i) continue; 
		// 현재 index번째 선택 시, 이전 선택 보다 작으면 선택 금지
		DAT[index] = i;
		bt(index + 1);
		DAT[index] = 0;
	}
}

int main() {
	bt(0);
}

 

출력

1 1 1
1 1 2
1 1 3
...
5 5 6
5 6 6
6 6 6

 

2. 중복이 불가능한 조합

3개의 주사위에서 R개의 숫자의 조합을 추출하는 경우, 중복을 허용하지 않고 순서를 고려하지 않는다.

코드

if (index > 0 && DAT[index - 1] >= i) continue; // 위의 조건에서 부등호만 변경해 주면 된다.
// 현재 index번째 선택 시, 이전 선택 보다 작거나 같으면 선택 금지

 

출력

1 2 3
1 2 4
1 2 5
...
3 4 6
3 5 6
4 5 6

 

실습

1. N Castle

n * n 크기의 체스판에서 n개의 룩을 배치할때 서로 공격하지 못하게 배치할 수 있는 경우의 수

룩은 상하좌우로 이동이 가능하다. 즉 같은 row 및 같은 col에 룩이 존재하면 안된다.

만약 n이 2라면 배치가 가능한 경우는 다음과 같다.

1 0		0 1
0 1		1 0

 

만약 1번 row에서 1번 col에 룩을 배치했다면 1번 row와 1번 col에는 룩을 배치할 수 없다. 2번 row와 2번 col에는 룩을 배치할 수 있다.

1번 row의 2번 col에 룩을 배치했다면 2번 row에는 1번 col에 룩을 배치할 수 있다.

 

n이 3이라면 배치가 가능한 경우는 다음과 같다.

1 0 0	1 0 0	0 1 0	0 1 0	0 0 1	0 0 1
0 1 0	0 0 1	1 0 0	0 0 1	1 0 0	0 1 0
0 0 1	0 1 0	0 0 1	1 0 0	0 1 0	1 0 0

 

N이 1일 경우 = 1

N이 2일 경우 = 2

N이 3일 경우 = 6

N이 4일 경우 = 24

즉 N!이 정답이 된다.

 

N의 8일때의 예시 코드

#include <iostream>

using namespace std;

char board[8][9]; // 디버깅용 배열
int DAT[8];
int cnt = 0;
// 룩 : '#'
// 체스판 : '_'

void place(int row) {
	//기저
	if (row >= 8) {
		cnt++;
		return;
	}
	for (int col = 0; col < 8; col++) {
		//판별
		if (!DAT[col]) {
			//처리
			board[row][col] = '#';
			DAT[col] = 1;
			//재귀 호출
			place(row + 1);
			//복구
			board[row][col] = '_';
			DAT[col] = 0;
		}
	}
}

int main() {
	for (int r = 0; r < 8; r++) {
		for (int c = 0; c < 9; c++) {
			board[r][c] = '_';
		}
	}
	place(0);
	cout << cnt;
}

 

출력

40320