알고리즘/백준

[백준] 9663 N-Queen

CGNY 2024. 10. 7. 12:48

https://www.acmicpc.net/problem/9663

 

백트레킹 문제이다.

어렵고 까다롭지만 좋은 문제라서 따로 정리해두려고한다.

더 좋은 풀이는 https://cryptosalamander.tistory.com/58 이분의 풀이를 추천드린다.

 

풀이 흐름

해당문제는 일단 하나의 row에 하나의 퀸만 배치할 수 있다는 것을 전재로 두는게 좋다.

탐색 자체는 현재 row(행)의 특정 col(열)에 퀸을 배치할 수 있는지 없는지를 판단할 것이다.

현재 row라는 값이 필요하기 때문에 탐색할 때 param으로 현재 현재 ‘row’를 받아와야한다.

row의 특정 col에 조건을 따져 배치할 수 있다면 배치하고 그렇지 않다면 되돌아 가준다.

계속 배치를 하다가 row가 n과 같다면 한 row당 하나의 퀸을 배치한 것이므로 ret의 값을 증가시켜준다.

 

순서는 첫번째 행의 빨간 화살표가 가르키는 순서대로 탐색을 할 것이다.

 

 

처음에 0행에 배치할 수 있기때문에 방문 표시를 해준다.

 

 

그리고 두번째 행의 어떤 열에 탐색할 수 있는지 확인한다. 1번째 행의 0열, 1열은 배치할 수 없고 3열에 배치할 수 있으므로 방문 표시 해준다.

 

2행도 확인해준다. 아래처럼 배치할 수 있는 열이 하나도 없다. 그러므로 return하여 뒤로 백한다. 이때 방문했던 곳의 방문 여부도 해제를 해주어야한다.

 

 

그럼 다시 0행으로 돌아와서 1열 부터 검사하는데 0행 1열은 방문이 가능하니 표시해두고 그다음 행으로 가준다.

 

그 다음 행인 1행의 경우 0, 1, 2열은 배치가 안되고 마지막 3열의 경우 배치가 가능하고,

그 다음 행인 2행의 경우 0열애 바로 배치가 가능하니 다음 행으로 넘어간다.

마지막 3행의 경우 0, 1열은 배치가 안되고 2열이배치가 가능하다.

위의 로직을 반복하면서 n행까지의 퀸을 다 배치 했다면 결과값을 증가시켜 가장 마지막에 결과값을 출력하면 된다.

 

구체적인 코드 풀이 방법

 

우선 퀸의 특성상 같은 행, 열, ‘/’ 대각, ‘\’ 대각에는 다른 퀸을 배치하지 못한다.

행과 열의 경우에는 그렇다 쳐도 ‘/’ 대각과 ‘\’ 대각을 어떻게 판별하는지가 중요한 점중 하나이다.

 

예를 들어보자, 만약 (0, 1)에 퀸을 배치한경우 모든 0행과 1열에는 퀸을 배치하지 못한다.

(0, 1)에 해당하는 ‘/’ 대각에도 퀸을 배치 하지 못한다. 이는 (0 + 1)은 1이고 그다음 행인 (1, 0)의 경우에도 (1 + 0)을 하면 1이 나온다.

 

즉 ‘/’ 대각은 row + col이 같다면 ‘/’ 대각에 있다는 것으로 판단할 수 있다.

두번째로 ‘\’ 대각의 규칙을 살펴보면, 만약 퀸을 (2, 3)에 두었다 가정하고 (3, 4)에 퀸을 두려고 시도한다고 해보자.

(2 - 3)은 -1이고 (3 - 4)도 -1이다. 즉 row - col이 같다면 ‘\’의 대각에 있다고 판단할 수 있다.

 

(아래 코드의 주석을 읽어보고 표현식을 이해하는 것도 중요하다.)

 

코드

 

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;

#define endl "\n"
#define ll long long
#define ROW first
#define COL second


// 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다는 것을 전재로 깔아두는 것이 좋다.

int n, ret = 0;
bool v1[40];	// 열을 차지하고 있는지
bool v2[40];	// '/' 방향 대각선을 차지하고 있는지
bool v3[40];	// '\' 방향 대각선을 차지하고 있는지

// curRow번째 row(행)에 퀸을 배치할 예정이다.
void dfs(int curRow)
{
	// n개를 놓는데 성공 했다면
	if (curRow == n)
	{
		++ret;
		return;
	}

	// (curRow, i) 에 퀸을 놓을 예정이다.
	for (int i = 0; i < n; ++i)
	{
		// 열이나 대각선 중에 방문한게 있다면 continue이다.
		// - v3의 표현식을 잘 이해해야한다. n이 15인 경우 첫 for문 가장 마지막이 curRow(0) - 14 + n - 1이 된다. curRow가 0익 i가 14인경우 방문 배열의 0번째 인덱스 값을 맞추기 위한 보정값이라 생각하면된다.(curRow - i + n - 1)
		// - 현재 행이 0이고 i가 0인경우 v3[14] = 1이되고, curRow가 14이고 i가 14인경우에도 v3[14] = 1이 되기 때문에 '\' 방향 대각선 방문 여부를 확인 할 수 있다.
		if (v1[i] || v2[i + curRow] || v3[curRow - i + n - 1]) continue;

		v1[i] = 1;
		v2[i + curRow] = 1;
		v3[curRow - i + n - 1] = 1;
		dfs(curRow + 1);
		v1[i] = 0;
		v2[i + curRow] = 0;
		v3[curRow - i + n - 1] = 0;
	}
}

int main(void)
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	dfs(0);
	cout << ret;
}