N-Queen

시간복잡도 계산

(1) 브루트포스 방식 → NxN 칸에 퀸이 있는지 없는지 하나하나 계산 → 2의 N제곱 승

(2) 하나의 행에 퀸이 놓여져있다면, 그 행에는 퀸이 또 놓여질 수 없다. 즉 하나의 행 당 퀸 하나가 놓여질 수 있는 경우의 수는 N, 총 N개의 행이 있으므로 → N의 N제곱

(3) 하나의 열에도 퀸은 유일해야한다. 따라서 처음 선택할 때는 N개의 경우의 수, 두 번째에서는 N-1개의 경우의 수, … 이런 식이므로 → N!

calc(row) : row행에서 퀸을 어디에 놓을 지 결정하는 함수

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

int n; // Queen의 개수
// int board[16][16] = {0, };

bool check_col[15]; 
bool check_dig[40]; 
bool check_dig2[40]; 

// 이 row와 col에 queen이 존재하는 지 검사
bool check(int row, int col) {
	if (check_col[col])
		return false;
	if (check_dig[row + col])
		return false; 
	if (check_dig2[row - col + n])
		return false;
	return true; 
}

int calc(int row) {
	if (row == n) return 1; 
	int cnt = 0; 
	for (int col = 0; col < n; col++) {
		if (check(row, col)) {
			// board[row][col] = true;
			check_col[col] = true; 
			check_dig[row + col] = true;
			check_dig2[row - col + n] = true; 

			cnt += calc(row + 1);
			
			// board[row][col] = false;
			check_col[col] = false;
			check_dig[row + col] = false;
			check_dig2[row - col + n] = false;
		}
	}
	return cnt; 
}

int main() {
	cin >> n; 
	cout << calc(0) << endl;	
	return 0; 
}

스토쿠

(1) 빈칸을 찾는다 (2) 빈칸에 1부터 9까지를 넣었을 때 행, 열에 그 숫자가 포함이 되어있는지 확인한다. (3) check 함수 : 행, 열을 검사해서 해당 숫자가 있으면 false, 없으면 true를 반환한다. 빈칸 개수 x 9 x 9

#include <iostream>
using namespace std; 

int board[9][9];

bool check(int row, int col, int num) {
	for (int c = 0; c < 9; c++)
		if (board[row][c] == num) return false;
	for (int r = 0; r < 9; r++)
		if (board[r][col] == num) return false;
	return true;
}

// 빈 칸을 찾아 적절한 수로 채운다.
void solve() {
	for(int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == 0) {
				for (int num = 0; num < 9; num++) {
					if (check(i, j, num)) {
						board[i][j] = num; 
						break;
					}
				}
			}
		}
}

int main() {
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			cin >> board[i][j]; 
	solve(); 
	for (int i = 0; i < 9; i++){
		for (int j = 0; j < 9; j++)
			cout << board[i][j] << " "; 
		cout << endl;
	}
	return 0; 
}

3x3 정사각형 검사 안했음 !!

해설

백트래킹 : 모든 경우를 호출하는 브루트포스와 달리, 조건에 맞지 않는 부분은 애초에 호출하지 않는다.

solve(int z) : z에 채울 번호를 선택하는 함수 (1) z = y * 9 + x => "" y = z / 9, x = z % 9 "" (2) y 행에 해당 숫자가 있는지 검사 (c[i][j] : i번 행에 j숫자가 있으면 true) (3) x 행에 해당 숫자가 있는지 검사 (c[i][j] : i번 열에 j숫자가 있으면 true) (4) 작은 정사각형에 해당 숫자가 있는지 검사 (c[i][j] : i번 작은 정사각형에 j 숫자가 있으면 true) (y, x) 는 (y / 3) * 3 + (x / 3)번째 작은 정사각형에 위치해있다. 즉 (z / 27) * 3 + (z % 9)/3이 된다. ex) (5, 2) 는 3번째 작은 정사각형에 위치해있다. (y / 3) * 3 + (x / 3) = 1 * 3 + 0 = 3

#include <iostream>
#define FOR(i) for(int i = 0; i < 9; i++)
using namespace std; 

int board[9][9]; 
bool c1[9][9], c2[9][9], c3[9][9]; 

int subSquare(int i, int j) {
	return (i / 3) * 3 + (j / 3); 
}

// index번째에 들어갈 수를 선택하는 함수
void selectNumber(int index) {
	if (index == 80) {
		FOR(i) {
			FOR(j) cout << board[i][j] << " ";
			cout << endl;
		}
		exit(0); 
	}
	int y = index / 9, x = index % 9; 
	if (board[y][x] != 0) // 이미 채워져있으므로 바로 다음 차례 검사
		selectNumber(index + 1); 
	else { // 빈 칸인 경우
		FOR(num)
			// 행, 열, 작은 정사각형에 포함되어있지 않은 숫자를 발견하면
			if (!c1[y][num] && !c2[x][num] && !c3[subSquare(y, x)][num]) {
				board[y][x] = num; 
				c1[y][num] = true;
				c2[x][num] = true;
				c3[subSquare(y, x)][num] = true; 
				
				selectNumber(index + 1); 

				board[y][x] = 0; 
				c1[y][num] = false;
				c2[x][num] = false; 
				c3[subSquare(y, x)][num] = false;
			}
	}

}

int main() {

	FOR(i) FOR(j) {
		cin >> board[i][j]; 
		if (board[i][j] != 0) {
			c1[i][board[i][j]] = true;
			c2[j][board[i][j]] = true;
			c3[subSquare(i, j)][board[i][j]] = true; 
		}
	}
	
	selectNumber(0); 

	return 0;
}