[백준] 9663번 N-Queen C++ 풀이

---

알고리즘 분류

• 브루트포스
• 백트래킹

---

문제 설명

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

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

---

입력 설명

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

---

출력 설명

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

---

예제 입력

8

---

예제 출력

92

---

아이디어

실제로 배열에 퀸의 위치를 기록하지 않고

퀸이 놓여있는 열과 퀸이 놓여있는 좌표만 기록한다.

그리고 하나의 행과 열에는 무조건 퀸이 한 개만 존재할 수 있으므로

0행부터 n-1행까지 재귀적으로 내려가면서 같은 행과 같은 열 그리고 대각선 경로에 겹치는 퀸이 없는 자리에만 다음 퀸을 놓는다.

모든 행에 겹치지 않게 퀸을 하나씩 놓았다면 경우의 수를 1 증가시킨다.

만약 겹치는 자리라면 return으로 이전 단계로 돌아가며 백트래킹을 사용한다.

---

알고리즘

0행부터 n-1행까지 순차적으로 진행하므로 같은 행에 퀸을 놓는 경우의 수는 존재하지 않는다.

따라서 같은 열인지 파악하기 위한 배열을 선언하고 대각선인지 파악하기 위해 지금까지 놓은 퀸의 위치를 기록할

퀸벡터를 선언한다. 지금까지 놓은 퀸의 위치와 현재 좌표가 대각선에 위치해 있는지 파악하는 방법은

| 퀸의 x좌표 - 현재 x좌표 | 가 | 퀸의 y좌표 - 현재 y좌표 | 라면 해당 퀸과 현재 좌표가 서로 대각선에 위치해 있는 것이다.

우리는 지금까지 놓은 모든 퀸의 경로와 중복되는 경로에 또 다른 퀸을 놓아서는 안 되기 때문에 퀸벡터에 있는 모든 퀸의 좌표와 현재 좌표를 비교해서 모두 대각선에 위치해 있지 않을 때 비로소 퀸벡터에 현재 좌표를 추가한 후 다음 행으로 넘어갈 수 있다.

---

코드

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
int N,ans=0;
vector<pair<int,int>> queenvec;
void Queen(vector<bool> line, int x, int y)
{
	if(line[y]) return;
	if(x==N-1)
	{
		ans++;
		return;
	}
	line[y] = true;
	for(int i=0; i<N; i++)
	{
		if(line[i]) continue;
		bool enter = true;
		for(auto &a : queenvec)
		{
			if(abs(a.first - (x+1)) == abs(a.second-i))
			{
				enter = false;
				break;
			}
		}
		if(enter)
		{
			queenvec.push_back({x+1,i});
			Queen(line,x+1,i);
			queenvec.pop_back();
		}
	}
}
int main()
{
	cin>>N;
	vector<bool> line(N,false);
	for(int i=0; i<N; i++)
	{
		queenvec.push_back({0,i});
		Queen(line, 0, i);
		queenvec.pop_back();
	}
	cout<<ans;
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/9663

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!