[BOJ/C++] 백준 9663번: N-Queen

 

🔗 문제 링크 : https://www.acmicpc.net/problem/9663

 

---

 

문제

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

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

 

 

 

 

 

입출력 예시

입력

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

 

 

출력

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

 

 

 

입출력 예시

 

 

 

---

 

풀이 

여덟 퀸 문제를 일반화한 퍼즐 문제인, N-Queen 문제이다.

백트래킹 기법으로 해결하는 게 일반적이므로 백트래킹을 익히는데 도움이 된다.

 

• Queen 은 상하, 좌우, 대각선까지 공격이 가능한 말이다.
  • 위 특징(특히 좌우 공격)을 이용하여, 첫 번째 퀸은 체스판의 첫 번째 줄, 두 번째 퀸은 체스판의 두 번째 줄에 배치하는 식으로 문제를 해결할 수 있다.

• 아래 풀이는 N개의 퀸을 배치하기 위해 PlaceQueen()을 재귀호출 하게 된다.
  • 0번째부터 N-1번째 퀸의 배치를 위해 PlaceQueen(0)을 시작으로 PlaceQueen(N-1)까지 호출한다.
  • PlaceQueen(N)을 호출한 경우, 문제의 조건을 모두 충족시킨 퀸의 배치가 완료된 것이므로, count를 1 증가시킨다.
• 다음 퀸의 배치를 위한 재귀호출 직전에는, 현재 선택한 퀸의 배치로 영향을 주는 칸(isUsed[])을 기억해서 다음 퀸의 배치를 결정한다.

 

🧩 isUsed의 쓰임

• `isUsed0 배열`은 상하, 즉 '해당 열이 다른 퀸으로부터 영향을 받는가?'에 대한 정보를 담고 있다.
• 예를 들어, `isUsed0[1]`이 `true`인 경우, 체스판의 1열은 다른 퀸의 영향을 받는 열이라는 것을 알 수 있다.
• 그림으로 보면 아래와 같다.

isUsed0

 

 

 

• `isUsed1 배열`은 '해당 좌하-우상 대각선이 다른 퀸으로부터 영향을 받는가?'에 대한 정보를 담고 있다.
  • N x N의 체스판에서는 대각선이 2N - 1개 존재한다.
• 예를 들어, `isUsed1[0]`과 `isUsed1[3]`이 `true`인 경우, 아래 그림처럼 해당 대각선은 다른 퀸의 영향을 받는 자리임을 알 수 있다. 

isUsed1

 

 

 

• `isUsed2 배열`은 '해당 좌상-우하 대각선이 다른 퀸으로부터 영향을 받는가?'에 대한 정보를 담고 있다.
• 예를 들어, `isUsed2[0]`, `isUsed2[3]`, `isUsed2[4]`가 `true`인 경우, 아래 그림처럼 해당 대각선은 다른 퀸의 영향을 받는 자리임을 알 수 있다.

isUsed2

 

 

전체 풀이는 아래와 같다.

#include <iostream>
using namespace std;

bool isUsed0[20];    // 상하
bool isUsed1[20];    // 대각선 (좌하-우상) x+y
bool isUsed2[20];    // 대각선 (좌상-우하) x-y
int N;
int count = 0;

void PlaceQueen(int n) {
    /* 퀸을 N개 모두 배치한 경우 */
    if (n == N) {
        count++;
        return;
    }

    for (int i = 0; i < N; i++) {
        /* 퀸끼리 서로 공격이 가능한 자리인 경우 */
        if (isUsed0[i] || isUsed1[n + i] || isUsed2[n - i + N - 1]) continue;
        
        isUsed0[i] = true;
        isUsed1[n + i] = true;  
        isUsed2[n - i + N - 1] = true; 
        PlaceQueen(n + 1);
        isUsed0[i] = false;
        isUsed1[n + i] = false;  
        isUsed2[n - i + N - 1] = false; 
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> N;
    PlaceQueen(0);
    cout << count;
}

 

 

 

---