[BOJ 9663] N-Queen (C++)

www.acmicpc.net/problem/9663

9663번: N-Queen

N-Queen 문제

구현 방법

N-Queen 문제는 전형적인 백트래킹 문제입니다.

 

백트레킹이란 탐색을 진행하면서, 답이 될 수 없는 경우에 도착하면, 다시 되돌아가 다른 경우를 수행하는 탐색 기법입니다.

 

N-Queen 문제에서는 n x n 체스판에 n개의 퀸을 서로 공격하지 않게 두는 경우의 수를 출력하는 문제입니다.

 

이 문제에서 퀸 같은 경우에는 가로, 세로, 대각선 모두 공격할 수 있으므로, 만약 새로 퀸을 놓으려는 자리가 이전에 있었던 퀸의 공격을 받을 수 있는 자리면 다시 되돌어가 다른 자리에 놓으며 답을 찾아내는 방식입니다.

 

1) 함수 정의

func(int cur) 함수는 (cur,0) , (cur, 1) , ... , (cur, n) 중 어디에 퀸을 놓을 수 있는지 결정하는 함수입니다.

즉, 체스판에서 cur번째 줄의 어느 칸에 놓을수 있는지 판별하는 함수입니다.

 

예를 들어 func(2)은, 퀸을 0번째, 1번째 줄에는 잘 놨고, 2번째의 어느 칸에 퀸을 놔야 할지 결정하는 함수입니다.

 

2) 퀸을 놓을 수 있는지 구별 하는 방법

이제 func함수가 나아가면서 퀸을 놓을 수 있는 자리에만 놔야 합니다.

이를 알기 위해 isused1, isused2, isused3 배열을 사용했습니다.

 

isused1 배열: 사전에 배치한 퀸으로부터 공격받을 수 있는 행 표시

위 사진처럼, (1,1)에 퀸을 놓은 상태면 (n, 1)에는 퀸을 놓을 수 없습니다.

위 상황에선, isused1 배열을 다음과 같이 설정해줍니다.

 

isused1[i] = 1; ((cur,i)에 퀸을 놓은 경우)

[ 0 , 1 , 0 , 0]

 

 

isused2 배열: 사전에 배치한 퀸으로부터 공격을 받을 수 있는 ↗ 방향 대각선 표시

위 사진처럼, (1,1)에 퀸을 놓으면 (2,0), (0,2)에는 퀸을 놓을 수 없습니다. (빨간색 숫자는 isused2 배열의 index)

즉, 사전에 퀸을 놓은 좌표의 x값과 y값의 합이 같은 칸에는 퀸을 놓을 수 없습니다.

위 상황에선, isused2 배열을 다음과 같이 설정해줍니다.

 

isused2[cur + i] = 1 ((cur,i)에 퀸을 놓은 경우)

[ 0 , 0 , 1 , 0 , 0 , 0 , 0 ]

 

 

isused3 배열: 사전에 배치한 퀸으로부터 공격을 받을 수 있는 ↘ 방향 대각선 표시

위 사진처럼, (1,1)에 퀸을 놓으면 (0,0), (2,2), (3,3)에는 퀸을 놓을 수 없습니다. (빨간색 숫자는 isused3 배열의 index)

이는 사전에 퀸을 놓은 좌표의 x값과 y값의 차이와 같은 칸에는 퀸을 놓을 수 없습니다.

위 상황에선, isused3 배열을 다음과 같이 설정해줍니다.

 

isused3[cur-i+n-1] = 1; ((cur,i)에 퀸을 놓은 경우)

[ 0 , 0 , 0 , 1 , 0 , 0 , 0 ]

 

 

위 내용을 아래와 같이 구현했습니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

//n x n 체스 판 크기
int n;
int cnt;

//퀸의 세로방향으로 공격 받을 수 있는지
int isused1[16];

//퀸의 / 방향 대각선으로 공격 받을 수 있는지
int isused2[30];

//퀸의 \ 방향 대각선으로 공격 받을수 있는지
int isused3[30];

//func함수는, (cur, i)에 퀸을 놓을 수 있는지 판별하는 함수
void func(int cur){

	//n번째 줄까지 퀸을 놓고 도달했으면 카운트 증가
    if(cur == n) {
        cnt++;
        return;
    }
	
    //(cur, 0), (cur, 1) , ...  , (cur, n) 까지 탐색
    for(int i=0;i<n;i++) {

        //공격 받을 수 있는 위치면 스킵
        if(isused1[i] || isused2[cur+i] || isused3[cur-i+n-1]) continue;

        //놓을 수 있는 자리면 놓고,
        //해당 자리에 놓으면서 공격가능한 루트 체크
        isused1[i] = 1;
        isused2[i+cur] = 1;
        isused3[cur-i+n-1] = 1;

        func(cur+1);

        //퀸을 다시 빼면서 체크했던 공격 루트 취소소
        isused[i] = 0;
        isused2[i+cur] = 0;
        isused3[cur-i+n-1] = 0;
    }

}

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

    cin >> n;

    //백트래킹 시작
    func(0);
    cout << cnt;
}

이 게시글은 바킹독님의 강의 영상을 보고 공부하여 작성한 글입니다

강의 링크: youtu.be/Enz2csssTCs