[백준] 30242번 N-Queen (Easy) C++ 풀이

 

---

알고리즘 분류

• 백트래킹

---

문제 설명

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

 N이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 것은 쉽다.

이 문제에서는 몇 개의 퀸이 이미 놓여있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.

---

입력 설명

첫 번째 줄에 정수 N이 주어진다. (1≤N≤20)

두 번째 줄에 정수 Q1, Q2, Q3,...,QN이 주어진다. Qi는 i번째 행에 있는 퀸의 열의 번호를 의미한다. (0≤Qi≤N)

만약 Qi가 0이라면 i번째 행에는 퀸이 놓여있지 않다는 뜻이다.

퀸이 서로 공격하는 올바르지 않은 상태의 입력 혹은 N개의 퀸이 모두 놓여있는 경우의 입력은 없다.

---

출력 설명

첫 번째 줄에 정수 A1, A2, A3, ⋯를 출력한다. Ai는 i번째 행에 있는 퀸의 열의 번호를 의미한다. (1≤Ai≤N)

만약 N개의 퀸을 놓을 수 없다면 -1을 출력한다.

---

예제 입력

3
0 0 0

4
0 0 0 0

4
3 0 0 0

4
0 0 0 1

10
3 0 0 0 0 0 0 0 0 0

19
0 0 2 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 10

---

예제 출력

-1

2 4 1 3

3 1 4 2

-1

3 1 6 9 5 10 8 4 2 7

1 5 2 6 17 12 8 19 14 18 15 7 3 11 9 4 13 16 10

---

아이디어

이미 주어진 퀸의 자리가 있으니 그 자리의 가로 세로 대각선이 안 겹치는 자리에 새로운 퀸을 놓으면서

모든 행을 다 채울 때까지 내려간다.

만약 이미 해당 행이 채워진 상태라면 그다음 행으로 바로 내려간다.

해당 열이 채워진 상태라면 다음 열로 넘어간다.

모든 행에 퀸을 하나씩 채웠다면 이를 출력하고 종료한다.

---

알고리즘

해당 열에 퀸이 있는지 판단하는 line 1차원 벡터, 퀸의 좌표 x, y를 저장하는 queen 1차원 벡터를 선언한다.

입력받은 퀸의 열에 해당하는 line의 값을 true로 바꾸고 queen에 해당 x와 y를 기록한다.

겹치는 행이 있으면 바로 다음 행으로 넘어가고

겹치는 열이 있으면 바로 다음 열로 넘어간다.

겹치는 행도 열도 없다면 겹치는 대각선이 있는지 판단한다.

겹치는 대각선은 다른 퀸의 x좌표 - 현재 x좌표가 다른 퀸의 y좌표 - 현재 y좌표와 같다면 같은 대각선 상에 위치해 있는 것으로 파악 가능하다.

이와 같은 조건을 모두 통과했다면 현재 위치는 퀸을 놓을 수 있는 자리이므로

line[현재y]을 true로 바꿔주고 queen[현재x] = 현재 y를 저장한다.

이를 재귀적으로 반복하다가 x가 n+1이 되는 시점이 오면 모든 행을 퀸으로 채운 것이므로 queen벡터를 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
int N;
bool flag = false;
void Queen(vector<bool> line, vector<int> &queen, int x, int y)
{
	if(flag) return;
	if(x>=N+1)
	{
		flag = true;
		for(int i=1; i<=N; i++)
			cout<<queen[i]<<" ";
		return;
	}
	if(line[y]) return;
	for(int i=1; i<=N; i++) if(queen[i] != 0 && abs(i-x) == abs(queen[i]-y)) return;
	line[y] = true;
	queen[x] = y;
	for(int i=1, j=1; j<=N; j++)
	{
		if(flag) return;
		if(queen[x+i])
		{
			i++;
			j = 0;
			continue;
		}
		Queen(line, queen, x+i, j);
	}
	queen[x] = 0;
}
int main()
{
	cin>>N;
	vector<bool> line(N+1,false);
	vector<int> queen(N+1,0);
	for(int i=1, j; i<=N; i++)
	{
		cin>>j;
		if(j!=0)
		{
			line[j] = true;
			queen[i] = j;
		}
	}
	for(int j=1, i=1; j<=N; j++)
	{
		if(flag) break;
		if(queen[i])
		{
			i++;
			j = 0;
			continue;
		}
		Queen(line, queen, i, j);
	}
	if(!flag) cout<<-1;
	return 0;
}

---

후기

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

---

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

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