[GDSC Week3-4] 백준 9663번:: N-Queen (C++)

* 생각한 아이디어 및 문제 풀이

체스에서 queen의 특성은 거리와 상관없이 모든 방향으로 움직일 수 있다.
n*n 정사각형 안에 n개의 queen을 배치하는 문제로, queen들은 자신의 일직선상 및 대각선상에 아무 것도 놓이면 안된다.
Queen함수에서는 각각 단계별로 퀸이 존재할 수 있는 여부를 확인한다.
isUsed1는 같은 열에 퀸이 존재하는지, isUsed2는 우상대각선에 퀸이 존재하는지, isUsed3는 좌상대각선에 퀸이 존재하는지 확인한다. (가로의 인덱스가 i, 세로의 인덱스가 j일때 우상대각선은 i+j가 모두 일치, 좌상대각선은 i-j=0이다.)
만약 (level, i)에 퀸을 둘 수 없다면 isUsed1, isUsed2, isUsed3를 모두 true로 변경하고 Queen(level+1)을 호출한다.

 

* 코드

#include<iostream>
using namespace std;

int N;
int cnt=0;
bool isUsed1[40]; //같은 열에 퀸 존재 여부
bool isUsed2[40]; //우상 대각선에 퀸 존재 여부
bool isUsed3[40]; //좌상 대각선에 퀸 존재 여부

void Queen(int level){
    if(level==N){
        cnt++;
        return;
    }
    for(int i=0; i<N; i++){
        if(isUsed1[i] || isUsed2[i+level] || isUsed3[level-i+N-1]) continue;
        isUsed1[i] = true;
        isUsed2[i+level] = true;
        isUsed3[level-i+N-1] = true;
        
        Queen(level+1);
        isUsed1[i] = false;
        isUsed2[i+level] = false;
        isUsed3[level-i+N-1] = false;
    }
}

int main(void) {
	ios::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> N;
	Queen(0);
	cout << cnt;
}

 

* 회고

 

 

* 문제 링크 : 

 

n*n 정사각형 안에 n개의 queen을 배치하는 문제로, queen들은 자신의 일직선상 및 대각선상에 아무 것도 놓이면 안 됩니다.

queen은 거리와 상관없이 모든 방향으로 움직일 수 있다.

10초는 10^9승이다.

경우의 수는 N*N.. N이 14일때 14^2개의 후보가 있다.

즉 ,N^2 * N^2 * ... N^2이 N개인 256의 14승이 된다.

 

백트레킹(가지치기)방법.

 

4가지 후보 중 가지치기하여 되는 케이스 선정

코드를 구현하려면 for문으로 돌린다.

solve(level)로 if(n~)

for(1~N)

 

 

 

우상대각선은 i+j가 모두 일치하는.

i-j는 좌상대각일치

j>i => i-j<0

1-N+@=0

 

 

처음에 상태를 보면서 버릴 수 있는 것은 버리고 시작하는 것이 매우 중요하다.

(N^2)^N = > N^N

 

 

NM시리즈가 백트레킹 , 조합론에 매우 유용함.

재귀는 dp, dfs, 트리에서 모두 많이 쓰인다.

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

9663번: N-Queen

https://blog.encrypted.gg/945