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

1. 개요

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

9663번: N-Queen

1-1. 설명

N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을때 퀸을 놓는 방법의 수를 구하는 프로그램을 구현한다. 

1-2. 제한 사항

 - 첫줄에 N이 주어지며, N은 1 이상 15미만

---

2. 구현

2-1. 풀이

백트래킹 방법으로 구현해본다. 백트래킹은 간단하게 설명하자면 DFS로 탐색하는 중, 방문 중인 노드가 유망한지 체크한다. 체크했을 때 유망하지 않으면 가지치기하여 이전으로 되돌아가는 알고리즘이다. 백트래킹으로 구현하는 N-Queens는 처음이라, 유튜브 강의와 자료에서 풀이를 토대로 구현하였다. 다른 알고리즘으로는 N-Queen을 풀어봤지만, 백트래킹은 처음이었다. 조금 더 연습해봐야겠다. 

2-2. 코드

#include <iostream>
#include <cmath>
using namespace std;

int cols[15];
// 열은 저장된 변수, 행은 index

int N, result = 0;

void backTracking(int idx);
bool isPromising(int idx);

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

    // N-Queen 
    // Backtracking 방법
    // 주의 : 2차원 배열보다 1차원으로 저장하는 것이 나음
    // 같은 열 기준으로 행, 대각선 기준을 판단하므로 열 중복이 일어나지 않음

    cin >> N;

    for (int i = 0; i < N; i++) {
        cols[0] = i; // 맨 윗줄에 첫 퀸 둠
        backTracking(0);
    }
    cout << result;

    return 0;
}

void backTracking(int idx) { // 백트래킹
    if (isPromising(idx)) { // 겹치는 위치에 없으면
        if (idx == N - 1) result += 1; // N-1열까지 검사 완료
        else {
            for (int i = 0; i < N; i++) { 
                cols[idx + 1] = i; 
                backTracking(idx + 1); // 다음 행 검사
            }
        }
    }
}

bool isPromising(int idx) {
    for (int i = 0; i < idx; i++) {
        if ((cols[idx] == cols[i]) || (abs(cols[idx] - cols[i]) == (idx - i))) return false;
        // 행이 같거나 대각선 위치에 있을 때 false
    }
    return true;
}