[c++] 백준 9663 N-Queen

백준 단계별로 풀어보기 [백트래킹] N-Queen

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

9663번: N-Queen

 

[풀이]

배치된 퀸이 n개가 되면 경우의 수 증가, 새로운 퀸은 배치된 퀸의 같은 행, 같은 열, 대각선에 위치해서는 안된다. 따라서 어차피 한 행에 하나의 퀸 밖에 놓지못하므로 이차배열을 사용하지 않고 col[]배열을 선언해 사용한다. col[1] = 1은 첫번째 열에 위치한 퀸의 행이 1행임을 의미한다. (x, y)와 (a, b)에 대해서 두 좌표가 대각선에 위치한다면 a-x == b-y 임을 이용하여 퀸의 배치 위치를 확인한다. 새로운 퀸이 배치 가능하다면 nqueen을 호출하여 다음 행으로 이동한다.

 

[코드]

#include <iostream>

int col[16]; // 각 열에 몇 번째 행에 퀸이 있는지 저장. 어차피 한 행에 퀸은 하나씩밖에 못 놓음.
int n, result;

bool check(int level)
{
    for (int i = 0; i < level; i++)
        if (col[i] == col[level] || abs(col[level] - col[i]) == level - i) //같은 행, 대각선인지 체크
            return false;
    //col[i]: x좌표, i: y좌표. (x, y)와 (a, b)에 대해서 두 좌표가 대각선에 위치한다면 a-x == b-y. 
    return true;
}

void nqueen(int row)
{
    if (row == n)
        result++; // n번째 퀸을 놓으면 경우의 수 증가
    else
    {
        for (int i = 0; i < n; i++)
        {
            col[row] = i; // row번 째 행, i번 째 열에 퀸 배치
            if (check(row)) // 가능하다면 다음 행으로 이동
                nqueen(row + 1);
        }
    }
}

int main() {
    std::cin >> n;
    nqueen(0);
    std::cout << result;
}