[백준] 9663 N－Queen

9663. N－Queen 풀이

난이도: Gold IV
문제 주소: https://www.acmicpc.net/problem/9663

문제 풀이

이 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 1 이상 15 미만의 자연수 N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성해야 한다.

처음에는 2차원 배열과 재귀 함수를 활용하여 모든 방향을 탐색하는 방식으로 코드를 작성했다.

 

bool check(int r, int c)
{
    bool check = true;
    for (int i = 1; i <= N; i++ ) {
        for (int dir = 0; dir < 8; dir++) {
            int x = c + dx[dir] * i;
            int y = r + dy[dir] * i;
            if (x < 1 || x > N || y < 1 || y > N) continue;
            if (chess[y][x] == 1) return false;
        }
    }
    return check;
}

 

이런 구조로 문제를 풀게 되면 퀸을 놓을 때마다 dx, dy 배열을 이용해 8방향으로 뻗어나가며 다른 퀸이 존재하는지 2중 반복문으로 일일이 확인해야 한다.

이렇게 풀게 되면 탐색 깊이가 깊어질수록 매번 보드 전체를 확인하는 것과 같은 오버헤드가 발생하지만 제한시간이 10초라 통과할 줄 알았다 하지만 시간 복잡도 분석을 잘 못했는지 시간 초과가 발생하여 다른 풀이를 찾게 되었다

 

for (int i = 1; i <= s; i++) {
    if (line1[r + i] || line2[s + r - i] || chess[i]) continue;
    line1[r + i] = line2[s + r - i] = chess[i] = true;
    n_queen(r + 1, s);
    line1[r + i] = line2[s + r - i] = chess[i] = false;
}

 

이번에는 퀸을 놓을 때마다 모든 방향을 탐색하는 대신 열을 담당하는 chess 배열과 두 대각선을 담당하는 line1, line2 배열을 활용해 상태를 미리 기록해두는 방식을 사용했다. 행과 열의 합(r + i)이 일정한 우하향 대각선과, 행과 열의 차(s + r - i)가 일정한 우상향 대각선의 성질을 인덱스로 활용했다.

결과적으로 퀸을 배치할 때 line1[r + i] || line2[s + r - i] || chess[i] 조건만 참조하여 퀸이 있는지 없는지만 확인하고 없다면 퀸을 배치하고 true로 업데이트한 뒤 다음 탐색을 이어가게 된다
처음에는 구현에 가까운 문제인줄 알고 풀기 쉬울줄 알았는데 한번 막혀버리니 완전 새로운 풀이를 고민하고 대각선을 어떤 규칙으로 마킹해야할지 고민하는 시간이 굉장히 오래걸렸다

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>

using namespace std;

bool chess[16];
bool line1[31];
bool line2[31];
int sol;
void n_queen(int r, int s)
{
    if (r > s) {
        sol++;
        return;
    }
    for (int i = 1; i <= s; i++) {
        if (line1[r + i] || line2[s + r - i] || chess[i]) continue;
        line1[r + i] = line2[s + r - i] = chess[i] = true;
        n_queen(r + 1, s);
        line1[r + i] = line2[s + r - i] = chess[i] = false;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    n_queen(1, n);
    cout << sol;
    return 0;
}

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 12015 - 가장 긴 증가하는 부분 수열2  (0)	2026.04.08
[백준] 11404 - 플로이드  (0)	2026.04.03
[백준] 10814 - 나이순 정렬  (0)	2026.04.01
[백준] 10942 - 팰린드롬?  (0)	2026.03.23
[백준] 2166 - 다각형의 면적 풀이  (0)	2026.03.22