BOJ 9663 N_Queen

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

9663번: N-Queen

올 2월 겨울방학 스터디 때 교수님이 backtracking 소개를 해주시며 처음 접하게 된 문제로, 가장 기본적인 backtracking 문제이다.

 

brute force를 이용한 문제 해결의 시간 복잡도를 알아보면,

해당 위치에 퀸을 놓을 수 있는지 확인하는 possible 함수가 $O(N^N)$ 번 호출되는데, 그 때마다 $O(N)$ (혹은 $O(N)$) 시간을 들여 그 자리에 놓을 수 있는지 없는지를 판별하게 된다.

 

따라서  $O(N^(N+1))$이라는 말도 안 되는 시간이 걸리게 된다.

 

위 경우는 가지치기가 없이 이미 그 자리에 놓을 수 없음이 알려진 경우에도 다음 level에 퀸을 놓을 수 있을지 탐색하는 brute force를 이용한 비효율적인 경우로, 가지치기(더이상 탐색이 무의미한 경우, 탐색을 이어나가지 않음)가 이루어지는 backtracking의 경우,  $O(N!)$ 정도면 해결 가능하다.

 

 

코드

#include <cstdio>
#include <vector>

using namespace std;
int N, cnt=0;
struct P {int x, y;};

bool possible(vector<P> &pos, int x) { // x위치에 퀸을 놓을 수 있는지 확인하는 함수
	// pos[i] = i level에 있는 퀸의 위치
    for(int diagonal = 1, i = pos.size()-1;i>=0;--i,++diagonal) {
        if(pos[i].x == x) return false; // 수직 방향(같은 x좌표)
        if((pos[i].x == x+diagonal) || pos[i].x == x-diagonal) // 대각선
            return false;
    }
    return true;
}

int nQueen(vector<P> &pos, int x, int y) {
    if(y>=N-1) return cnt+=1;
    for(int i=0;i<N;++i) {
        if(possible(pos,i)) { // 다음 레벨의 i위치에 놓는게 가능하면
            pos.push_back({i,y+1}); // 다음 level에 퀸 추가
            nQueen(pos, i, y+1);
            pos.pop_back(); // i위치에 놓은 퀸 제거
        }
    }
    return 0;
}

int main() {
    scanf("%d",&N);
    for(int i=0;i<N;++i) { 
        vector<P> pos;
        pos.push_back({i,0});
        nQueen(pos,i,0);
    }
    printf("%d",cnt);
    return 0;
}

 

nQueen 함수에서는 다음 level의 i위치에 i를 놓을 수 있는지 pos 벡터는 현재 놓인 퀸의 위치를 저장한다.

따라서 다음 level의 i 위치에 놓을 수 있음이 확인되면(possible i), pos 벡터에 다음 level에 놓을 수 있는 퀸의 위치를 먼저 push 한 후, nQueen 함수를 호출한다.

 

i위치에 퀸을 놓을 수 있을지 확인하는 방법은 크게 두 가지로, 1. 2차원 배열에 퀸의 위치와 이동 가능한 경로를 저장하는 방법과, 2. 위의 방법처럼 i위치에서 위로 한 칸씩 올라가며, 위, 대각선 방향으로 다른 퀸이 위치하는지 확인하는 방법이 있다. 2번 방법을 이용하면 $O(N)$) 시간에 확인이 가능하다.