[백준/BOJ] 9663번 N-Queen (C/C++)

 

백준 온라인 저지(BOJ) 9663번 N-Queen

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

* 사용언어 : C언어, C++

 

1. 문제

N * N 체스판에 퀸 N개를 배치했을 때 서로 공격할 수 없도록 놓는 방법의 수를 출력

(퀸은 가로, 세로, 대각선을 거리 제한 없이 이동하며 공격할 수 있음)

 

2. 풀이

DFS를 활용하는 전형적인 형태의 백트래킹 문제입니다.

 

2차원의 체스판이 있다고 했을 때 row를 DFS의 깊이로 보고

각 column을 배치되는 위치로 보고 DFS로 풀었습니다.

(각 row에 1개의 퀸만 배치 가능 → 각 row에서 어떤 column을 사용하냐를 결정하는 DFS)

 

 

통상 DFS는 visited라는 배열을 만들고 해당 노드를 방문했다고 1로 표시하는 것이 일반적인데,

이 문제는 각 row에서 퀸이 어느 column에 배치됐다를 기록하게 했습니다. (배열 이름도 cols로 명명)

 

각 row가 사용할 column은 재귀 함수인 recursion 함수를 통해 매칭되는데

해당 row가 각각의 column에 대해 가능한지 여부를 확인하는 promising 함수를 구현했습니다.

promising 함수에서는 이미 배치된 위쪽 row들을 차례로 보면서 c에 둘 경우 세로나 대각선에 위치하는지를 확인합니다.

int promising(int r, int c) {
	for (int y = 0; y < r; ++y) {
		if (cols[y] == c) return 0; // 세로(같은 컬럼) 상에 있으면 unpromising
		if (abs(y - r) == abs(cols[y] - c)) return 0; // 대각선 상에 있으면 unpromising
	}
	return 1; // promising
}

 

이 문제에서는 0부터 사용해도 무관하여 배열의 크기를 14로 잡았는데

다른 DFS 문제는 1부터 사용해야 하는 경우도 있으니 그럴 경우 크기 + 1로 선언해야 합니다.

 

그 외 풀이는 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9663_N-Queen
1112KB	4688ms
*/
#include <cstdio>

const int LM = 14;
int cols[LM], N, cnt;

int abs(int a) {
	return a > 0 ? a : -a;
}

int promising(int r, int c) {
	for (int y = 0; y < r; ++y) {
		if (cols[y] == c) return 0;
		if (abs(y - r) == abs(cols[y] - c)) return 0;
	}
	return 1;
}

void recursion(int r) {
	if (r >= N) {
		++cnt;
		return;
	}

	for (int c = 0; c < N; ++c) {
		if (promising(r, c)) {
			cols[r] = c;
			recursion(r + 1);
		}
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	recursion(0);
	printf("%d\n", cnt);
	return 0;
}