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

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

8

 

예제 출력 1 

92

 

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

 

문제 출처

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

9663번: N-Queen

 

---

 

문제 해결 방법

• 백트래킹 알고리즘을 이용하여 문제를 해결하였다.
• 이 문제는 혼자서 풀기 벅차 구글링을 통하여 문제 해결 방법을 찾아보았다. 

 

• 이 문제는 퀸의 특성상, 체스판에서 한 행(Column) 당 한 개의 퀸만 존재할 수 있다는 것을 전제로 깔아두고 시작하는 것이 좋다고 한다. 이 전제를 이용하면 다음과 같이  2차원 배열을 만들지 않고, 1차원 배열로 문제를 해결할 수 있다. 
• 위의 그림을 1차원 배열로 표현하면 다음과 같다.

column[0] = 1 (0번째 열의 1행에 퀸 존재) column[1] = 3 (1번째 열의 3행에 퀸 존재) column[2] = 0 (2번째 열의 0행에 퀸 존재) column[3] = 2 (3번째 열의 2행에 퀸 존재)

• 이렇게 한 행씩 퀸을 배치해가면서 총 배치 행수가 N이 되면 조건을 만족하는 경우의 수를 1개씩 늘려주는 방식으로 백트래킹을 진행할 수 있다.
• 따라서 함수의 매개변수에는 현재 몇 번째 행을 채우고 있는지를 기록하는 인자(level)를 넣어줘야 한다.
• 백트래킹을 진행하면서 체크해야할 점은 다음과 같다.

1. 임의로 배치한 퀸이 다른 퀸과 같은 행(열)에 속하는가?
2. 임의로 배치한 퀸이 다른 퀸과 대각선에 위치해 있는가?

bool Promising(int level) {
    for (int i = 0; i < level; i++) {
        // 대각선이거나 같은 라인, column[i] : x 좌표, i : y좌표
        if (column[i] == column[level] || abs(column[level] - column[i]) == level - i) {    
            return false;
        }
    }
    return true;
}

 

코드

#include <iostream>
using namespace std;

#define MAX_SIZE 15

int N, cnt;
int column[MAX_SIZE];

bool Promising(int level) {
    for (int i = 0; i < level; i++) {
        // 대각선이거나 같은 라인, column[i] : x 좌표, i : y좌표
        if (column[i] == column[level] || abs(column[level] - column[i]) == level - i) {    
            return false;
        }
    }
    return true;
}

void nQueens(int x) {
    if (x == N) {
        cnt++;
    }
    else {
        for (int i = 0; i < N; i++) {
            column[x] = i;    // 퀸 배치
            if (Promising(x)) {     // 유효할 경우 다음 행의 퀸 배치, 유효하지 않다면 다른 위치로 퀸 배치
                nQueens(x + 1);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    nQueens(0);
    cout << cnt << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [백트래킹]
• 골드IV

 

참고 사이트

• https://namu.wiki/w/%EC%97%AC%EB%8D%9F%20%ED%80%B8%20%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 나무위키