백준 [9663] N-Queen

백트래킹을 이용한 문제.

 

생각한 방법은 3가지였다. 3번째 방법이 내가 적용한 풀이다.

 

1. 2차원 배열을 선언해, 퀸이 배치 될 때, 퀸의 경로에 1을 더해서, 다음 퀸이 이 자리에 오지 못하게 한다.

만약, 다른 퀸의 경로하고 겹치는 경우 1을 또 더해준다.

아래 그림이 예시다.

하지만, 이렇게 되면, 퀸 배치를 옮길 때, 복구 작업도 해줘야 하기 때문에,

시간이 오래걸리고, 코드도 깔끔하게 나오진 않았다.

 

2. 매 탐색마다, N 크기를 1씩 줄이기

어떤 자리에 퀸이 들어왔단 것은 해당 행과 열엔 퀸이 들어오지 못하니,

다음 재귀함수에선 (N-1 * N-1)만큼의 크기를 검사하는 방식

여기서 문제는 위의 그림에서 보듯이, 2번째 퀸이 3번째 열에 배치되면, 2번째 열에 퀸을 배치할 수 있음에도 불구하고 건너뛰게 되므로 올바른 해결 방법은 아니었다.

 

3. 퀸들의 x좌표 기록

2번째 방법에서 개량한 방법이다.

해당 라인의 퀸 배치가 결정되면, x좌표를 기록하고, 다음 행으로 넘어간다.

이렇게 하면,  더이상 해당 행은 고려 대상이 되지 않는다.

즉, 일차원 배열만으로 문제를 해결 할 수 있게 된다.

 

이제, 고려 대상은 2가지로 줄여진다.

1. 이전 퀸들의 x좌표 값을 가지는지(같은 열(y축)에 있으면 안 되니),

2. 이전 퀸들과 대각선 관계인지

 

코드는 다음과 같다.

 

#include <iostream>
#include <math.h>
using namespace std;
// 각 라인 퀸의 x좌표 기록
int board[16] = { 0, };
int maxLine, ans = 0;

int queen(int currentLine)
{
	int currentX, beforeLine, flag;
	if (currentLine == maxLine + 1)
		ans += 1;
	else
	{
		// 현재 라인의 x축 탐색
		for (currentX = 1; currentX <= maxLine; currentX++)
		{
			flag = 1;
			board[currentLine] = currentX;
			for (beforeLine = 1; beforeLine < currentLine; beforeLine++)
			{
				// 이전 라인 퀸들과 같은 X 좌표를 가지는지 ||
				// 대각선의 위치에 있는지
				if (board[beforeLine] == board[currentLine] || 
					(abs(board[beforeLine] - board[currentLine]) == currentLine - beforeLine))
				{
					// 있으면 다음 X 좌표 탐색 
					flag = 0;
					break;
				}
			}
			// 없으면 밑에 칸 탐색
			if (flag)
				queen(currentLine + 1);
		}
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> maxLine;
	queen(1);
	cout << ans;
	return 0;
}