[백준 9663] N-Queen

너무나도 유명한 문제이다.

세상에 수많은 풀이 방법이 공개되어있으니 한번 검색해보는 것을 추천한다.

 

이 문제는 널널한 시간을 줬음에도 불구하고, 아무생각 없이 모든 경우를 탐색하면 시간초과이다.

여기서 내가 말하는 모든 경우 탐색이란, Queen을 같은 칸이 아닌 곳에 일단 박아놓고 Queen끼리 서로 공격할 수 있는지 확인하는 무지성 방법이다.

대충 시간복잡도 계산해보면,

• 퀸을 놓는 경우 = \(O( _{225}P_{15})\)
• 서로 공격할 수 있는지 확인하는 데 걸리는 시간 = \(O(15^2)\)

매 경우마다 공격할 수 있는지 확인해야하니 둘을 곱하면.... 대충 생각해봐도 어질어질한 수치이다.

 

그래서 이 문제는 처음부터 서로 공격하지 못하게 놓는게 포인트이다.

 

그렇게 하기 위해 Queen은 8방향 모두 움직일 수 있다는 특성을 이용하자.

Queen이 8방향을 다 갈 수있다 == 어떤 Queen 하나를 놓았을 때, 이 Queen이 속하는 행, 열, 대각선 2개 위에 더 이상 다른 Queen이 올라오면 안된다는 것이다.

 

그럼 어떻게 코딩할 것인가 ?

재귀함수는 x번 행에서 y번 열에 Queen을 놓을 수 있는지 확인한다. y번 열에 놓을 수 있는지 판단하기 위해서, (x, y)의 값을 통해

• x번 행 위에 Queen이 존재하는지
• y번 열 위에 Queen이 존재하는지
• (x, y)를 포함하고 왼쪽 위에서 오른쪽 아래로 떨어지는 대각선 위에 Queen이 존재하는지
• (x, y)를 포함하고 오른쪽 위에서 왼쪽 아래로 떨어지는 대각선 위에 Queen이 존재하는지

를 보면 된다.

만약 놓을 수 있다면, (x, y)가 속한 모든 선을 true로 바꿔주고 다른 행으로 넘어가면 된다.

 

대각선을 판단하는게 좀 어려울 수도 있는데, 이것만 알아두면 된다.

• 왼쪽 위에서 오른쪽 아래로 떨어지는 "같은" 대각선에 속한 칸들의 (행 - 열) 값은 모두 동일하다.
• 오른쪽 위에서 왼쪽 아래로 떨어지는 "같은" 대각선에 속한 칸들의 (행 + 열) 값은 모두 동일하다.

코드를 보자.

 

#include <bits/stdc++.h>
using namespace std;

bool row[16]; // 행
bool col[16]; // 열
bool crossFromRight[31]; // 대각선 오른쪽 위에서 왼쪽 아래
bool crossFromLeft[31]; // 대각선 왼쪽 위에서 오른쪽 아래
int n;

void setFlag(int& line, int& i, bool flag) {
	row[line] = col[i] = crossFromRight[line + i] = crossFromLeft[i - line + 15] = flag;
}

void recur(int line, int& cnt) {
	// n개의 라인에 Queen을 모두 놓은 경우
	if (line == n) {
		cnt++;
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (!row[line] && !col[i] && !crossFromRight[line + i] && !crossFromLeft[i - line + 15]) {
			setFlag(line, i, true);
			recur(line + 1, cnt);
			setFlag(line, i, false);
		}
	}
}


int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int cnt = 0;
	cin >> n;

	recur(0, cnt);

	cout << cnt;

	return 0;
}

내 코드는.. 좀 많이 느린 편이다. 구글링을 통해 더 빠른 코드들을 구경해보는 것도 좋을 것 같다.

0ms 걸리는 코드들은 그냥 https://oeis.org/A000170 이걸보고 바로 답을 출력한 것 같다.