greentea31's Note

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

풀이 과정

NxN 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제이다.

유명한 백트래킹 문제이다. 체스판 위에 퀸을 하나 하나 놓아가면서 이전에 놓았던 퀸이랑 같은 행, 열, 대각선에 위치하면 여기에는 못놓는다 판정하고 다음 위치에 놓아보는, 이러한 과정을 코드로 구현하면 된다.

체스판에서의 퀸의 위치를 2차원 배열로도 표현할 수 있지만, board[i] = j (i번째 행에 j번째 열에 퀸이 존재함) 과 같이 1차원 배열로도 퀸의 위치를 나타낼 수 있다.

1차원 배열과 재귀함수로 백트래킹을 해가면서 답을 구하였다.

소스 코드

#include <iostream>
using namespace std;

int board[16];
int N, answer;
void nQueen(int y) { // y개의 퀸이 체스판 위에 존재함
    int ko;

    if (y == N) { // N개 다 놓았으면 정답을 증가시킴
        answer++;
        return;
    }

    for (int i = 0; i < N; i++) { // y번째 행의 i번째 행의 칸에 대해서
        ko = 1;
        for (int j = 0; j < y; j++) { // 이미 놓인 퀸들에 대해서
            if (board[j] == i || abs(i - board[j]) == abs(y - j)) {
                ko = 0; // 같은 열에 존재하거나, 대각선에 이미 퀸이 존재해서 배치 불가능
                break;
            }
        }

        if (ko) { // 배치 가능하면
            board[y] = i; // 배치하고
            nQueen(y+1); // y+1개의 퀸이 존재하는 체스판 위에서 알고리즘을 다시 시행함
        }
    }
}

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

    cin >> N;
    nQueen(0);

    cout << answer;
    return 0;
}