코딩 테스트 일기 - 16일 차

N-Queen

문제 링크 : N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로 된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인 경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한 사항

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

입출력 예

n	result
4	2

풀이 방법

• 백트래킹 알고리즘의 대표격인 N-Queen 문제로, 백트래킹 알고리즘을 활용하고자 했다.
• 행마다 퀸을 배치할 열을 저장해놓고, dfs를 통해서 다음 퀸을 배치할 수 있는 열을 검사한 후에 마지막 열까지 가능하다면 정답 개수에 추가했다.
  -> 백트래킹이기 때문에 정확한 시간복잡도 계산은 불가능하지만, O(N!)의 시간복잡도를 가지지만 pruning 전략으로 인해 그 정도의 시간복잡도를 가지지는 않을 것으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

bool check(int k, int n, vector<int>& visited){
    for(int i = 1; i < k; i++){
        // 같은 열인지, 같은 대각선인지 검사
        if(visited[i] == visited[k] || abs(visited[i] - visited[k]) == abs(i - k)){
            return false;
        }
    }
    return true;
}

int nqueen(int k, int n, vector<int>& visited){
    if(k > n){
        return 1;
    }
    
    int count = 0;
    for(int i = 1; i <= n; i++){
        visited[k] = i;
        if(check(k, n, visited)){
            count += nqueen(k + 1, n, visited);
        }
    }
    return count;
}

int solution(int n) {
    vector<int> visited(n + 1, 0);
    int answer = nqueen(1, n, visited);
    return answer;
}