[백준 9663번][C++] N-Queen

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

9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

풀이

🧠 Algorithm

문제 이해

우선 퀸(Queen)의 행마에 대해서 기본적으로 알아야 이 문제를 풀 수 있다.

 

퀸(queen)의 행마

퀸은 자신의 위치한 곳에서 가로 한줄, 세로 한줄, 대각선 양 옆으로 모두 공격이 가능하다.

그렇다면 우선 가로 공격을 피하기 위해 퀸을 한 줄에 한 개씩 위에서부터 차례로 배치해보고, 그 후 세로와 대각선 공격 가능 여부를 따져보자.

Backtracking (되추적 방법)

되추적 방법이란, 상태공간트리(모든 상태들을 나타낸 트리 구조)를 위에서부터 아래로 탐색하다가 유망하지 않은 노드들은 더이상 검색하지 않는 방식을 말한다.

여왕의 배치를 나타낸 상태공간트리

이 문제의 상태공간트리는 위와 같이 한 줄에 퀸 한개씩을 배치해나가는 모양으로 나타난다.

앞서 말했다시피 가로 공격은 피했지만, 아직 세로공격과 대각선 공격은 고려하지 못했으므로 이것이 일어나는지 판별해주는 작업이 필요하다. 이 작업이 바로 '유망'한지를 판별하는 작업일 것이다.

 

변수 설명

int g_count : 전역 변수로, 가능한 queen의 배치 개수를 저장한다.

int col[15] : 각 가로 줄의 queen들이 각각 위치한 세로 줄 index를 담은 list이다.

 

함수 설명 - promising

해당 상태가 유망한지, 즉 현재까지의 퀸들의 배치에서 공격이 일어지 않는가?를 말해주는 함수이다.

새로 배치한 idx번째 queen의 배치가 이전 queen들과 같은 세로줄, 또는 대각선 상에 존재하는 지에 대해 알려준다.

bool promising(int idx, int* col) {
	int k = 0;
	bool attack = false;
	while ((k < idx) && (!attack)) {
		if ((col[k] == col[idx]) || (abs(col[k] - col[idx]) == idx - k))
			attack = true;
		k++;
	}
	return !attack;
}

 

함수 설명 - queens

각 줄에 queen들을 배치하는 함수로, 현재까지의 배치가 가능한 것이라면, 다음 줄에 queen을 배치하고, 그렇지 않다면 다시 되돌아 가는 backtraking 방식을 채택한다.

이때 마지막 줄까지의 배치를 모두 마쳤다면, g_count를 1 증가시킨다.

void queens(int n, int idx, int* col) {
	if (promising(idx, col)) {
		if (idx == n-1)
			g_count++;
		else {
			for (int i = 0; i < n; i++) {
				col[idx + 1] = i; // 다음 줄에 queen을 배치함
				queens(n, idx + 1, col);
			}
		}
	}
}

 

🖥 CODE

#include <iostream>
using namespace std;
int g_count = 0; // 가능한 배치 개수를 세는 전역변수

// 현재 놓여진 퀸들의 배치가 가능한 것인지 알아봄
bool promising(int idx, int* col) {
	int k = 0;
	bool attack = false; // 공격이 일어나는가?
	while ((k < idx) && (!attack)) {
    	// 같은 세로줄에 있는지, 같은 대각선 상에 있는지 확인
		if ((col[k] == col[idx]) || (abs(col[k] - col[idx]) == idx - k))
			attack = true;
		k++;
	}
	return !attack;
}

// queen들을 체스판에 배치하는 함수
void queens(int n, int idx, int* col) {
	if (promising(idx, col)) { // 지금 모양이 가능한 것이라면,
     	// 만약 마지막이라면,
		if (idx == n-1)
			g_count++; // 가능한 배치 개수 하나 증가
        // 아직 배치할 남은 줄이 더 있다면,
		else {
			for (int i = 0; i < n; i++) {
				col[idx + 1] = i; // 다음 줄에 queen을 배치함
				queens(n, idx + 1, col);
			}
		}
	}
}

int main() {
	int N, col[15];
	cin >> N;
	queens(N, -1, col);
	cout << g_count << '\n';
	return 0;
}