[백준][C++] 9663번: N-Queen 풀이

 

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

9663번: N-Queen

 

N값이 주어졌을 때 퀸 N개가 N X N에서 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다.

 

일단 느낌이 올 때까지 N이 1일 때부터 그림을 그려가며 서로 공격할 수 없는 경우의 수를 구해봤다.

N이 4일 때 서로 공격할 수 없는 배치들을 그릴 때 살짝 감이 왔는데 같은 행과 열에는 퀸이 하나만 있다는 것을 알았다. 쉽게 생각해 퀸의 공격 방향을 보면 어느 좌표에 퀸이 있다면 같은 행, 열, 그리고 대각선에는 퀸이 존재할 수 없다.

 

이 논리를 가지고 어떻게 풀지 그림을 통해 4 X 4 크기일 때를 보자.

먼저 퀸의 위치를 어떻게 저장할 지가 고민이었고 막힌 부분이었다.

같은 열 또는 행에는 퀸이 하나 밖에 없다는 것을 이용해 column 배열을 만들어 퀸이 몇 번째 행에 있는지를 저장해줬다.

 

0번 열에는 퀸이 2번 행에 있다

 

퀸을 어떻게 저장할 지 정했으므로 (0,0)부터 (N-1,N-1)까지 앞에서 생각한 조건을 사용해 하나씩 퀸을 넣어 검사해보았다.

1. j가 0일때 퀸을 0~3까지 한 번씩 넣어본다.

2. 위 조건(같은 열,행, 대각선에는 퀸 존재 X)를 사용해 j값 이전까지의 퀸 들과 현재 퀸과의 위치 관계를 검사한다.

3. 공격할 수 있는 퀸이 없다면 j+1로 1,2번을 반복한다. (j까지는 서로 공격할 수 없는 배치 완성)

4. j가 N이 되면 N X N에서 N개의 퀸이 서로 공격할 수 없는 배치를 한 가지 찾은 것이다.

 

#include <iostream>

using namespace std;

int N, cnt=0;
int column[16];

bool check(int j) {
	// 행과 대각선에 퀸 있는지 검사
	for(int i=0; i<j; i++) {
		if(column[i]==column[j] || (j-i)==abs(column[j]-column[i])) {
			return true;
		}
	}
	return false;
}

void nqueen(int j) {
	if(j == N) {
		cnt++;
		return;
	}
	
	for(int i=0; i<N; i++) {
		column[j]=i;
		if(!check(j)) {
			nqueen(j+1);
		}
	}
}

int main(void) {
	cin >> N;
	
	nqueen(0);
	cout << cnt;
}