[BOJ 9663번/C++] N-Queen

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

9663번: N-Queen

N-Queen

문제

문제

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

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

입력

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

출력

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

 

풀이

백트래킹의 대표문제인 N-Queen 문제였다. 프로그래머스에도 동일한 문제가 있다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

체스판이라고 2차원 배열을 선언해서 놓을 필요는 없고, 1차원 배열을 이용해 이전 퀸이 놓인 위치만 저장해준다.

재귀를 돌면서 퀸을 놓을 수 있는 위치를 찾아야하는데, 같은 세로줄에 놓는 것은 판단하기가 쉽다.

하지만, 대각선의 경우 조금 생각을 해줘야 하는데 나는 아래와 같이 풀었다.

 

[ X, X, Q, X, X ]

[ X, X, X, X, X ]

 

인 상황이라면 다음 줄에 올 수 없는 위치는 3번째 칸, 2번째 칸, 4번째 칸이다.

이는 각각 왼쪽 대각선, 같은 세로줄, 오른쪽 대각선이다.

각 대각선의 위치를 (퀸 현재위치 ± 1) 이라고 생각해보자.

 

한줄이 더 늘어난 상태로 아래를 보자.

 

[ X, X, Q, X, X ]

[ O, X, X, X, O ]

[ X, X, X, X, X ]

 

첫 번째 줄의 퀸과 대각선으로 겹치는 자리는 1번째와 5번째이다.

이는 (퀸 현재위치 ± 2)와 같은데, 한 줄 씩 내려갈수록 더해지거나 빼지는 수가 1씩 늘어난다.

 

즉, (퀸 현재위치 ± (현재 추가할 줄 - 퀸이 위치한 줄)) 이 되었다.

 

이런 규칙을 그대로 코드에 반영해서 풀었더니 해결이 쉽게 완료되었다.

 

#include <iostream>

using namespace std;

int pos[14];
int q_count = 0;

void N_Queen(int p, int N) {
    if (p == N) {
        q_count++;

        return;
    }

    for (int i = 0; i < N; i++) {
        bool check = true;
        for (int j = 0; j < p; j++) {
            int left = pos[j] - (p - j);
            int right = pos[j] + (p - j);

            if ((left < 0 || i != left) && (right >= N || i != right) && (i != pos[j])) {
                continue;
            }

            check = false;
            break;
        }

        if (check) {
            pos[p] = i;
            N_Queen(p + 1, N);
        }
    }
}

int main() {
    int N;
    cin >> N;

    N_Queen(0, N);
    cout << q_count << endl;
    
    return 0;
}