[백준알고리즘] 9663번: N-Queen -C++

[백준알고리즘] 9663번: N-Queen -C++

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

백트래킹 문제로 유명한 N-Queen 문제다. 유명한 문제인만큼 정답 비율은 53%가 넘음에도 불구하고 골드 5의 난이도를 갖고 있는 문제다. 그만큼 중요한 문제라고 말하는 것 같다.

N-Queen 문제

 

 

N-Queen 문제는 원래 8 Queen 문제로 유명하다. 문제의 요구조건은 동일하나 \( 8 \times 8 \) 크기의 체스판에 8개의 퀸을 놓는 문제다. 이거에 대한 접근법도 다양하게 있던 것으로 기억한다. 아래는 위키백과에서 다루는 내용이다.

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

여덟 퀸 문제

 

 

예전에 풀었던 기억은 있었는데, 블로그를 보니까 Java로 풀었던 경험이 있다. 잘 쓰지 않고 있던 언어인데, 그때도 Java를 되게 오랜만에 썼나 보다.

[백준알고리즘] 9663번: N-Queen -Java (tistory.com)

[백준알고리즘] 9663번: N-Queen -Java

 

예전에 풀었던 풀이를 보니까 굉장히 백트래킹스러운 풀이 방법을 적용했다. 가능한 열의 집합을 따로 생각을 해줌으로써 오늘 풀이보다 더 빠르게 푼 것 같다.

 

오늘은 C++로 풀었으나, C++로 통과한 코드 중에서도 시간이 꽤 오래 걸린 코드다. 그래도 쉽게 접근해서 쉽게 해결했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

이번에는 예전에 Java로 풀었을 때보다 더 간단하게 접근했다.

 

먼저, 주어진 \(N\)에 따라서 체스판의 크기가 \( N \times N \)으로 결정된다.

 

퀸은 같은 줄에 놓지 못하기 때문에 하나의 퀸을 어디에 둘 지를 고민하면 된다. 따라서 위에서부터 한 줄씩 퀸을 놓는 것을 DFS의 각 레벨을 처리하는 것으로 여긴다. 

 

각각의 가로줄에서는 모든 칸에 퀸을 놓을 수 있는 경우에만 퀸을 놓고 다음 줄로 넘어가는 과정을 반복한다. 해당 가로줄에서 각 칸에 퀸을 둘 수 있는지는 아래의 표에서 표시한 영역을 검사한다. 즉, 해당 가로줄의 윗줄들에서 이미 놓인 퀸의 위치를 확인하는 것이다.

		Queen

 

 

위에 색칠한 칸만 직접 확인해주면서 이전에 퀸을 둔 자리가 아니면 된다. 그렇기 때문에 간단하게 문제를 해결할 수 있다.

 

위의 방식대로 C++로 푼 코드가 아래에 있다.

DFS 방식으로 한 줄씩 처리를 하는 함수가 countMethods 함수이며, 각각의 위치마다 board의 상황에 따라 Queen을 놓을 수 있는 지 판단하는 함수가 canPutQueen 함수다.

#include <iostream>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

bool canPutQueen(std::vector<std::vector<bool>>& board, int y, int x)
{
	// 좌상
	int d = 1;
	while (0 <= y - d && 0 <= x - d)
	{
		if (board[y - d][x - d])
			return false;
		d++;
	}

	// 상
	d = 1;
	while (0 <= y - d)
	{
		if (board[y - d][x])
			return false;
		d++;
	}

	// 우상
	d = 1;
	while (0 <= y - d && x + d < board[y].size())
	{
		if (board[y - d][x + d])
			return false;
		d++;
	}

	return true;
}

int countMethods(std::vector<std::vector<bool>>& board, int level)
{
	if (level == board.size())
		return 1;

	int width = board[level].size();
	int numberMethods = 0;
	for (int w = 0; w < width; w++)
	{
		if (!canPutQueen(board, level, w))
			continue;

		board[level][w] = true;
		numberMethods += countMethods(board, level + 1);
		board[level][w] = false;
	}

	return numberMethods;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::vector<bool>> board(n, std::vector<bool>(n, false));

	std::cout << countMethods(board, 0);
}