[boj] (g5) N-Queen

문제 링크

퀸 : 오와 열, 대각선 이동이 가능한 말

체스말이 움직일 수 있는 트리 구조는 아래와 같다.

문제 조건에서 퀸이 서로 공격할 수 없게 놓으라고 했으므로 (2,1) (2,2) 는 위치할 수 없는 자리이다.
체스 위치를 dfs로 완전 탐색하며 가능한 자리를 찾을 수도 있지만,
효율이 떨어지기 때문에 백트래킹으로 가능한 자리만 탐색, 즉 트리를 가지치기(Purning) 하여 효율성을 높일 예정이다.

• 한 행마다 하나의 퀸을 배치해가면서, 총 배치 열수가 N(N개의 퀸을 전부 배치)개가 되면, 경우의 수를 1개씩 늘려주는 방식으로 백트래킹을 진행
• 따라서, 재귀함수의 매개변수에는 현재 몇 번째 열을 채우고 있는지를 기록하는 인자가 필요
• 퀸을 배치해가면서 체크해야하는것은, "임의로 배치한 퀸이 다른 퀸과 같은 행 또는 같은 열에 있는가" 또는 "대각선에 위치해있는가"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int chess[15][15];
int N, cnt = 0;

bool isPossible(int row, int col) // 다른 퀸과 같은 행, 대각선에 있는지 판별
{
    // 열
    int x = row - 1, y = col;
    while (x >= 0)
    {
        if (chess[x][y] == 1)
            return false;
        x--;
    }

    // 위-왼쪽 대각선
    x = row - 1;
    y = col - 1;
    while (x >= 0 && y >= 0)
    {
        if (chess[x][y] == 1)
            return false;
        x--;
        y--;
    }

    // 위-오른쪽 대각선
    x = row - 1;
    y = col + 1;
    while (x >= 0 && y < N)
    {
        if (chess[x][y] == 1)
            return false;
        x--;
        y++;
    }

    return true;
}

void dfs(int row)
{
    if (row == N)
    {          // N개를 모두 채스판 위에 놓았으므로
        cnt++; // 경우의 수를 하나 증가시키고 함수 종료
    }
    else
    {
        for (int col = 0; col < N; col++)
        {
            if (isPossible(row, col) && chess[row][col] == 0)
            {
                chess[row][col] = 1; // 퀸 배치
                dfs(row + 1);        // 가능하면 다음 열로 이동
                chess[row][col] = 0; // 초기화
            }
        }
    }
}

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

    cin >> N;

    dfs(0);

    cout << cnt;

    return 0;
}