Mist16's Dev Blog

문제

• 9663번 : N-Queen
• Rank : Gold V
• 링크 : https://www.acmicpc.net/problem/9663

풀이 전략

• 퀸의 경우 상하좌우, 대각선으로 길이 제한 없이 이동할 수 있다.
  
  • -> 한 줄에 퀸은 하나만 존재할 수 있다.
• 1~N번째 행까지, 퀸을을 놓을 수 있는 모든 열에 퀸을 두어서, 경우의 수를 모두 더한다.

int queenBoard(int idx, QueenBoard qBoard)
{
	int answer = 0;

	if (idx == N)
		return 1;
	for (int i = 0; i < N; i++)
	{
    	answer += queenBoard(idx + 1, tempBoard);
	}
    return answer;
}

• 대각선 / 다른 행에 다른 줄의 퀸이 있을 경우 퀸을 놓을 수 없으므로, 퀸을 둘 때마다 보드에 해당 범위를 체크한다.
  • int [N][N]으로 구현할 경우 함수 호출 인자가 지나치게 기므로, 비트마스킹으로 구현하였다.
  • 퀸을 놓기 전, 해당 칸의 비트마스크가 0인지 확인하고, 0일 경우에 해당 퀸에 영향을 받는 칸을 비트마스킹 한 후 함수를 재귀 호출해준다.
  • 비트마스킹해야할 사항은 다음과 같다
    • Queen을 놓은 곳의 가로선
    • Queen을 놓은 곳으로부터의 대각선(X모양)

if ((qBoard.n[i] & (1 << idx)) == 0)
{
	QueenBoard tempBoard = qBoard;
	tempBoard.n[i] = tempBoard.n[i] | (1 << idx);
	for (int j = 1; j < N - idx; j++)
	{
		tempBoard.n[i] = tempBoard.n[i] | (1 << (idx+j));
	
		if (i - j >= 0)
		{
			tempBoard.n[i - j] = tempBoard.n[i - j] | (1 << (idx + j));
		}
		if (i + j < N)
		{
			tempBoard.n[i + j] = tempBoard.n[i + j] | (1 << (idx + j));
		}
	}
}

전체 소스 코드

//Backjoon Problem No.09663
//https://www.acmicpc.net/problem/9663
//Mist16, 2022-02-06
#include <iostream>

using namespace std;

int N;

struct QueenBoard
{
	unsigned int n[15] = { 0, };
};

int queenBoard(int idx, QueenBoard qBoard)
{
	int answer = 0;

	if (idx == N)
		return 1;
	for (int i = 0; i < N; i++)
	{
		if ((qBoard.n[i] & (1 << idx)) == 0)
		{
			QueenBoard tempBoard = qBoard;
			tempBoard.n[i] = tempBoard.n[i] | (1 << idx);
			for (int j = 1; j < N - idx; j++)
			{
				tempBoard.n[i] = tempBoard.n[i] | (1 << (idx+j));
				
				if (i - j >= 0)
				{
					tempBoard.n[i - j] = tempBoard.n[i - j] | (1 << (idx + j));
				}
				if (i + j < N)
				{
					tempBoard.n[i + j] = tempBoard.n[i + j] | (1 << (idx + j));
				}
			}
			answer += queenBoard(idx + 1, tempBoard);
		}
	}
	return answer;
}


int main()
{
	QueenBoard blankboard;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	cout << queenBoard(0, blankboard);
	
	return 0;
}

Note

• 비트마스킹을 쓰지 않을 경우 시간 초과로 실패하였다. 함수 호출이 잦을 경우, 함수로 전달되는 인자의 양에도 신경을 써야 할 것.