[백준/C++] 9663번 : N-Queen (백트래킹 연습)

N-Queen 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 

8

예제 출력 1 

92

---

백트래킹에 대해 공부하면서 소문이 자자한 N-Queen 문제를 풀어봤다.

백준 골드로 표시된 문제는 처음 풀어봐서 약간 긴장했는데, 아니나 다를까 체스의 ㅊ도 모르는데 무작정 퀸 배치한다고 문제 던져줘서 너무 난감했다..^^ 

 

퀸이 어떻게 배치되는지 체스에 대한 룰을 전혀 몰라서 아래 블로그를 통해 퀸이 어떻게 배치될 수 있는지에 대해서만 읽었다!! (혼자 풀어보고 싶어서 스크롤 더 내려보고 싶은 마음을 억제했다)

 

감사한 블로거님의 사진을 가져와서 보자면, 퀸이 위치한 네 면과 대각선에는 다른 퀸을 배치할 수 없다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
int arr[16];
int cnt = 0;

void DFS(int depth)
{
	if (depth == N)
	{
		cnt++;
		//for (int i = 0; i < N; i++)
		//	cout << arr[i] << " ";
		//cout << endl << "count : " << cnt << endl;
		return;
	}
	
	for (int i = 0; i < N; i++)
	{
		bool check = true;
		for (int j = 0, k = depth-1; j < depth; j++, k--)
		{
			// 현재 Depth에서부터 위로 한 칸씩 올라가며 대각선 판별
			if (arr[depth - j - 1] == i || abs(arr[depth - j - 1] - i) == abs(depth-k))
			{
				check = false;
				break;
			}
		}
		if (check)
		{
			arr[depth] = i;
			DFS(depth + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	DFS(0);

	cout << cnt;
	return 0;
}

 

처음 코드를 제출해서 맞은 소스코드는 위와 같다.

 

백트래킹 문제인 만큼 DFS를 이용하였고, 한 줄 한 줄 퀸이 배치될 수 있는 공간을 1차원 배열인 arr로 선언하였다.

DFS의 매개변수인 depth를 이용해 몇번째 행인지를 판단하고, arr의 인덱스를 이용해 몇번째 열인지를 판단하였다.

 

해당 문제의 핵심은 퀸의 대각선을 구분하는 방법이었는데, 나는 현재 Depth로부터 한 칸씩 위로 올라가며 이전에 놓여진 퀸들(arr 배열의 원소)의 위치를 보며 비교하였다.

 

위로 올라갈수록 arr 배열의 인덱스는 depth-j-1 가 되어 같은 열에 있는지 == i 를 통해 비교하고, 대각선에 있는지 k 를 통해 비교했다.

첫번째 for문인 i = 0부터 N까지는 현재 Depth에서 퀸이 어느 열에 놓일 수 있는지를 찾기 위함이고, 두번째 for문인 j = 0부터 depth까지는 이전에 놓인 퀸들의 위치를 비교하며 놓일 수 있는지를 찾기 위함이다.

 

여기서 나의 실수는 멍청하게 depth 위치에서부터 위로 거슬러 올라가며 arr 배열 요소를 비교하려 했다는 점이다..!!

그냥 첫번째 놓았던 arr[0] 번째 퀸부터 검사했으면 k값도 필요없고, arr[depth-j-i] 같은 복잡한 인덱스도 필요없었는데 당시 문제를 풀 때 생각이 거슬러 올라가야한다고 고정되어 있던 것 같다 ㅎㅎ;;

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
int arr[16];
int cnt = 0;

void DFS(int depth)
{
	if (depth == N)
	{
		cnt++;
		//for (int i = 0; i < N; i++)
		//	cout << arr[i] << " ";
		//cout << endl << "count : " << cnt << endl;
		return;
	}
	
	for (int i = 0; i < N; i++)
	{
		bool check = true;
		//for (int j = 0, k = depth-1; j < depth; j++, k--)
		for (int j = 0; j < depth; j++)
		{
			// 현재 Depth에서부터 위로 한 칸씩 올라가며 대각선 판별
			//if (arr[depth - j - 1] == i || abs(arr[depth - j - 1] - i) == abs(depth-k))
			//{
			//	check = false;
			//	break;
			//}

			// 첫번째 줄부터 한 칸씩 내려가며 대각선 판별
			if(arr[j] == i || abs(arr[j] - i) == abs(depth-j))
			{
				check = false;
				break;
			}
		}
		if (check)
		{
			arr[depth] = i;
			DFS(depth + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	DFS(0);

	cout << cnt;
	return 0;
}

 

문제를 성공하고 나서 다시 0에서부터 아래로 내려가며 같은 열과 대각선을 검사하는 코드를 작성해보았다.

이렇게 풀면 k 값도 필요없고 arr의 인덱스도 j만 들어가면 돼서 코드가 훨씬 간결하고 보기 좋아졌다.

 

대각선은 비교하고자 하는 퀸의 x, y 값과 현재 depth와 i 값을 x, y로 보고 각각끼리 빼서 절댓값이 같으면 대각선이다.

쉽게말하자면, abs(이전 퀸의 위치.X - 현재 위치.X) == abs(이전 퀸의 위치.Y - 현재 위치.Y) 가 되면 대각선에 위치한다는 뜻이다.

각 행 - 행, 열 - 열 의 절댓값이 같으면 된다는 뜻이다!

 

문제를 풀어보고 나서 다른분들의 블로그들을 보니 대각선을 구하는 과정에서 많은 어려움을 겪으신 것 같았다. 

나는 대각선을 구하는 방법(?)에 대해선 예전에 깨달은 적이 있어서 "절댓값을 이용하면 되겠구나~" 싶었는데, 혼자 거꾸로 비교하며 자체 하드모드를 즐겼다 ㅎㅎ;

---

https://kang-james.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9backtracking-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0-N-Queen-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4

[알고리즘] 백트래킹(backtracking) 알아보기(& N-Queen 문제 풀이)

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

9663번: N-Queen