[프로그래머스] N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

풀이

30분?
1학년 때 나를 절망하게 했던 n queen 문제이다. 당시에는 풀이하지 못하고 위키피디아에 있는 결과값들을 하드코딩하여 return하는 꼼수를 썼었는데, 다른 풀이를 봤을 때 그 방식을 이용한 풀이를 발견해서 웃음이 나왔다.
처음에는 문제 그대로 시뮬레이션하는 코드를 작성했는데, 이 방법으로는 시간제한이 걸릴 것을 알았지만 방법이 떠오르지 않아서 일단 코드를 작성했다. 작성한 코드로는 마지막 두개의 테스트케이스의 시간제한을 통과하지 못했고, 결국 1차원 배열만 사용하여 queen의 상태를 나타내는 풀이를 찾아 적용했다.

코드

// 02:22 ~ 
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int board[12] = {0,};
int n;
int cnt;

bool check(int col, int row){
    for(int i = 0; i <col; ++i){
        if(board[i] == row) return false;
        if(abs(col - i) == abs(board[i] - row)) return false;
    }
    
    return true;
}

void nqueen(int col){
    if(col == n){
        ++cnt;
        return;
    }
    
    for(int i = 0; i < n; ++i){
        if(check(col,i)){
            board[col] = i;
            nqueen(col + 1);
        }
    }
}

int solution(int _n) {
    cnt = 0;
    n = _n;
    
    nqueen(0);
    
    return cnt;
}