C++ / 백준 / 9663 / N-Queen

문제

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

9663번: N-Queen

문제풀이

처음에는 2차원 배열을 이용하여 풀었는데 시간 초과가 나서 다른 풀이를 참고했다.

퀸은 가로, 세로, 대각선으로 이동이 가능하다.

현재 위치에 퀸을 두면 가로줄에는 더 이상 퀸을 둘 수 없다는 점을 이용하여 1차원 배열을 y축 배열로 사용했다.

(board[y]가 0이면 (y, 0)에 퀸을, 1이면 (y, 1)에 퀸을 둔다는 의미이다.)

DFS를 사용했고, 현재 y위치를 인자로 넘겨주었다.

퀸의 x위치를 0부터 N-1까지의 수로 표시할 것이므로 빈 공간을 -1으로 두었다.

 

0부터 N-1까지 돌면서 현재 y줄에 퀸을 둔다 가정하면서 3가지의 경우의 수를 따진다.

현재 퀸 위치의  위쪽을 돌면서 퀸을 둔 적이 있는지,

왼쪽 대각선을 돌면서 퀸을 둔 적이 있는지,

오른쪽 대각선을 돌면서 퀸을 둔 적이 있는지를 따진다.

 

위쪽은 단순히 board[y]의 y를 0부터 y-1까지 돌면서 board[y]의 값과 같은지를 보면 된다.

왼쪽 대각선은 y2-y1 == x2-x1 인지 판별, 같으면 퀸을 못 두는 위치이므로 다음 x로 넘어간다.

오른쪽 대각선은 y2+x2 == y1+x1 인지 판별, 같으면 퀸을 못 두는 위치이므로 다음 x로 넘어간다.

 

세 조건을 모두 통과했으면 퀸을 두었으므로 다음 줄로 (y+1) 넘어간다.

그러다 y가 끝에 도달했으면 답 개수를 1 늘리고 return 한다.

NxN 체스판에서 N개의 퀸을 두어야 하므로 y가 끝에 도달하기 전에 끝나는 경우는 없다.

 

 

코드

#include <iostream>
#include <vector>
using namespace std;
int N, answer;
vector<int>board;

void DFS(int y) {
	int idx(0), prev(0);
	if (y >= N) {
		answer++;
		return;
	}
	for (idx = 0; idx < N; ++idx) {
		board[y] = idx;
		for (prev = 0; prev < y; ++prev) {
			if (board[prev] == board[y]) {
				board[y] = -1;
				break;
			}
			if ((y - prev) == board[y] - board[prev]) {
				board[y] = -1;
				break;
			}
			if ((y + board[y]) == (prev + board[prev])) {
				board[y] = -1;
					break;
			}
		}
		if (board[y] != -1) {
			DFS(y + 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;

	board = vector<int>(N, -1);

	DFS(0);

	cout << answer;
}