[백준] 9663번 N-Queen (C++)

문제

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

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

입력

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

예제 입력 1

8

출력

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

예제 출력 1

92

풀이

문제 해결 방법

이 문제는 백트래킹을 사용하여 해결할 수 있습니다. 주요 해결 단계는 다음과 같습니다:

1. 상태 체크: 각 위치에 퀸을 놓을 수 있는지 확인
   • 같은 열에 퀸이 있는지
   • 대각선 방향에 퀸이 있는지
2. 백트래킹:
   • 한 행씩 퀸을 놓아가며 진행
   • 불가능한 경우 이전 상태로 돌아가기
   • 모든 퀸을 놓은 경우 카운트 증가
3. 최적화:
   • 방문 배열을 사용하여 체크 속도 향상
   • 대각선 방향 체크를 위한 별도의 배열 사용

이 알고리즘의 시간 복잡도는 최악의 경우 O(N!)이지만, 실제로는 가지치기로 인해 더 빠르게 동작합니다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <algorithm>

int n, cnt;
int visitY[17];
int visitR[35];
int visitL[35];

void back(int x)
{
    int i;

    if (x == n + 1)
    {
        cnt++;
        return;
    }

    for (i = 1; i <= n; i++)
    {
        if (visitY[i] == 0 && visitR[x + i] == 0 && visitL[x - i + n] == 0)
        {
            visitY[i] = 1;
            visitR[x + i] = 1;
            visitL[x - i + n] = 1;
            back(x + 1);
            visitY[i] = 0;
            visitR[x + i] = 0;
            visitL[x - i + n] = 0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    back(1);
    printf("%d", cnt);

    return 0;
}