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

 

9663번: N-Queen

알고리즘 공부나 코딩 테스트를 준비하는 사람들이라면 꼭 한번 풀어봐야한다고 할 수 있을만큼 백트래킹을 대표하는 유명 문제다.
컴퓨터가 등장하기 훨씬 전부터 존재했던 문제로 8*8 크기의 체스판에 8개의 퀸을 배치하는 8-Queen 문제에서 시작되었다.

 

 

Chess에서 Queen은 N * N 크기의 체스판에 정확히 N개까지 서로의 이동 경로를 피해서 배치할 수 있다.
이동 방법도 복잡하지 않아서 프로그램으로 단순화해서 풀이하기도 쉬운 편이다.
N의 갯수가 15 미만인 것에서 흰트를 얻는다면 모든 경우의 수를 직접 따져봐야함을 알 수 있다.

 

 

하지만 이 문제를 처음 접하면 백트랙킹이나 브루트 포스에 대해 알고있더라도 막상 Queen을 놓는 상황과 앞서 놓은 Queen과의 위치 확인을 어떤 방식으로 표현할지 아이디어 찾기가 어려운 편이기도 하다.

 

 

 

---

 

 

문제의 포인트

Queen을 놓을 수 있는 자리인지 판단하기

백트래킹 알고리즘

 

 

Queen을 놓을 수 있는 자리인지 판단하기

Queen의 이동 방향

 

 

Chess에서 Queen은 상하좌우, 대각선 좌우와 위아래까지 자신 주변 8방향을 모두 움직일 수 있다.
따라서 같은 행과 열에는 하나의 Queen만 위치할 수 있게되며 N * N 크기의 체스판이라면 각 행 혹은 열에 하나씩만 배치한 N개의 Queen을 놓는것이 최대가 된다.

 

 

8 * 8 Chess board에서 8개의 Queen을 놓을 수 있는 해의 일부

 

 

이렇게 N개의 Queen을 놓을 수 있는 모든 경우의 수를 찾기 위해서는 하나씩 놓아보면서 모든 경우를 따져봐야 한다.
문제는 그럼 어떤 자리에 Queen을 놓을 수 있는지 어떻게 판단할 수 있는가 이다.

 

 

차라리 간선 정보가 주어지는 그래프 형태거나 맵 형태의 데이터를 이용해 길을 찾으려고 한다면 그 자체로 갈 수 있는 길인지 없는 길인지 쉽게 판단할 수 있다.
하지만 이 문제에서 길은 이전에, 또 그 이전에, 처음부터 위치시킨 Queen들에 의해 만들어진다.

 

 

Chess board를 좌표로 표현해보면 좌, 우 대각선 방향 좌표의 특징이 보인다.

 

 

앞에 놓인 퀸들에 의해 영향받는 위치인지 판단하기 위한 방법은 체스판을 배열로 여기고 그려보고 index를 표시해보면 어렵지 않게 발견할 수 있다.

 

 

우선 상하좌우로 얼마든지 움직일 수 있기 때문에 퀸이 놓인 행과 열에 대한 정보를 기록해두고 이용할 수 있다.
행을 체크하기 위한 1차원 배열을 만들고 각 index가 각 행을 의미하도록 사용하면 간단히 한번만 접근해서 해당 행에 놓아도 되는지 확인할 수 있다.

 

열도 마찬가지로 index를 이용해 해당 열에 이미 놓였는지를 체크해서 활용할 수 있다.
하지만 어차피 한 행/열에 Queen은 하나씩만 존재할 수 있기 때문에 탐색 방법을 한 행 씩, "하나 놓고 다음행으로" 와 같은 방식으로 접근해 본다면 행을 체크하기 위한 배열은 없어도 된다.

 

 

대각선 이동 역시 마찬가지 방법으로 행/열 대신 각 대각선에 놓아도 되는지를 확인하기 위한 check 배열을 이용할 수 있다.
어떻게 배열의 index 만 이용해서 대각선을 표현할 수 있을까?

 

index를 표시한 배열 그림을 보면 x좌표와 y좌표의 합 또는 차가 대각선과 관계있음을 눈치챌 수 있다.

예를 들어 x좌표와 y좌표의 차가 0이라면 (0, 0) 부터 시작해서 오른쪽 아래로 내려가는 대각선을 특정할 수 있다.
또 x좌표와 y좌표의 합을 따져보면, (0, 7)부터 시작해서 (7, 0)까지 왼쪽 아래로 내려가는 대각선 상에 있는 모든 x, y 좌표의 합이 7임을 알 수 있다.

 

 

각 대각선 역시 하나 이상의 퀸은 놓일 수 없기 때문에 이 방법을 이용하면 간단하게 몇개의 배열만으로 놓일 수 있는 자리인지 아닌 지 판단할 수 있다.

 

 

백트래킹 알고리즘

최단 경로를 찾는 문제가 아니므로 BFS가 아닌 DFS 형태로 한가지 경우 씩 끝까지 탐색해가면서 찾아 나가는 방식으로 접근하는 것이 좋다.
일단 더 이상 놓을 수 있는 자리가 없을 때 까지 퀸을 놓아보고 N개를 놓았는지 확인하는 방법으로 찾아가면 된다.
이런 방법을 Backtracking algorithm이라고 한다.

 

 

Backtracking 혹은 DFS의 경우 Stack 자료구조를 이용해서 While 문으로 마지막 선택을 꺼내는 방식으로 구현할 수도 있지만 일반적으로는 재귀 호출을 많이 이용한다.

 

 

재귀 함수의 구현이 특히 코딩 테스트에서는 익숙해지기 전까지 꽤 복잡하게 느껴질 수 있지만 N-Queen 문제만큼은 재귀 함수로 모델링 하기가 쉬운 편이다.
하나의 행마다 한번의 재귀 호출로, 함수 내에서는 가능한 열을 찾도록 sync를 맞춰보면 구현이나 디버깅이 그리 복잡해지지 않는다.

 

 

---

 

 

전체 Code

 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N, cnt;

int check_c[15 + 5];
int check_right_down[15 * 2 + 5];
int check_left_down[15 * 2 + 5];

void DFS(int r) {
	int c;

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

	for (c = 0; c < N; c++) {
		if (check_c[c]) continue;
		if (check_right_down[N - 1 + (c - r)]) continue;
		if (check_left_down[r + c]) continue;

		check_c[c] = check_right_down[N - 1 + (c - r)] = check_left_down[r + c] = 1;
		DFS(r + 1);
		check_c[c] = check_right_down[N - 1 + (c - r)] = check_left_down[r + c] = 0;
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	cin >> N;

	DFS(0);
	cout << cnt << "\n";

	return 0;
}