(백준/C++) 9663_N-Queen

백준 9663번: N-Queen (acmicpc.net) 문제는 백트래킹(backtracking) 문제의 대표 주자격인 문제입니다.

이 문제는 체스판에 퀸을 놓는 모든 가능한 방법을 찾을 때, 백트래킹 알고리즘을 사용합니다.

백트래킹이란, 해를 찾는 도중에 그 해가 정답이 될 수 없다는 것이 판명되면 즉시 다른 해를 찾는 방법입니다.

이 경우, 퀸을 놓을 수 있는지 여부를 확인하고, 놓을 수 없으면 다른 퀸을 놓을 필요 없이 바로 다음 위치로 넘어갑니다.

주의사항

이 문제에서는 주의사항이라고 해야 할지… 몇 가지 고려해야 할 사항이 있습니다.

1. 퀸을 놓는 위치를 선택할 때, 행 or 열, 대각선에 이미 퀸이 있는지를 확인해야 합니다. 이는 퀸이 모든 방향을 공격할 수 있다는 체스의 규칙 때문입니다. 따라서 각 행, 열, 대각선에는 하나의 퀸만 존재해야 하고, 이를 검사할 방법을 생각하셔야 합니다.

2. 추가적으로 체스 판을 생각해볼 수 있습니다. 직관적으로 체스 판은 2차원 행렬이라고 생각할 수 있지만, 말은 퀸 한 종류라는 점과, 두다 보면 한 줄에 하나씩 놓게 된다는 점. 그리고 검사해야 할 내용이 위의 1번과 같이 행 or 열, 대각선에 위치해있는지에 대한 정보라는 것을 알 수 있게 됩니다.

사실, 큰 고려사항은 아닙니다. 2차원 행렬로 문제를 풀고 나면 모든 칸을 검사하지 않고 간단한 계산만으로 대각선을 계산할 수 있다는 것 또한 생각해볼 수 있다는 것 뿐입니다.

퀸의 공격 범위

---

접근법

1. 배치

하나의 줄 내에서 모든 칸에 하나씩 두고, 모든 퀸을 두었다면 (NxN에서 N개의 퀸을 두었다면), 해를 찾은 것이므로 가능한 경우의 수를 1 증가시킵니다.

(이 단계에서 기저사례를 설정합니다.)

2. 확인

배치를 했다면 중간에 해당 위치에 퀸을 놓을 수 있는지 확인해야 합니다. 이 단계에서는 이전에 놓은 퀸들과 같은 행 or 열, 대각선에 없는지를 확인해야 합니다.

이때, 배치를 할 수 없다고 판단된다면 그 이후의 경우의 수는 없기 때문에 빠르게 해당 해를 제거하는 것이 백트래킹입니다.

---

풀이

저는 위 접근법에 따라 두 개의 함수로 만들어봤습니다.

또한, 같은 대각선에 위치해 있는지 확인하는데 필요한 정보는 행과 열에 대한 정보입니다.
즉, 왼쪽 대각선 방향(row - col)과 오른쪽 대각선 방향(row + col)이 같은지 확인하기 위해서는, 2차원 배열을 예로 들면 각 index에 대한 정보만 있으면 가능합니다.

따라서, 1차원 배열로 index(row)와 값(col)만 있으면 대각선 여부까지 검사할 수 있습니다.

#include <iostream>
#include <vector>
using namespace std;

int SIZE, COUNT = 0;
vector<int> rowcol;

//확인
bool check(int row) 
{
	for(int r = 0; r < row; r++)
	{
		if (rowcol[r] == rowcol[row] || //같은 열에 위치한 퀸이 있는지 확인
			r - rowcol[r] == row - rowcol[row] || //왼쪽 대각선 방향의 퀸이 있는지 확인
			r + rowcol[r] == row + rowcol[row]) //오른쪽 대각선 방향의 퀸이 있는지 확인
			return false;
	}

	return true;
}
//배치
void place(int row) 
{
	if (row == SIZE) //모든 행에 퀸을 배치했다면 해를 찾음
	{
		COUNT++;
		return;
	}

	for(int c = 0; c < SIZE; c++) //각 열에 대해
	{
		rowcol[row] = c; //퀸을 배치하고
		if (check(row)) //배치할 수 있는지 확인
			place(row + 1);
	}
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> SIZE;
	rowcol.resize(SIZE);

	place(0);
	cout << COUNT;
}