백준 9663번 : N-Queen

• 분류: 백트래킹

코드

#include <iostream>

int n;
int count=0;
int col[15];

void dfs(int startRow) {
    if(startRow == n) {
        count++;
        return;
    }
    for(int j=0 ; j<n ; j++) {
        if(col[j]==-1) {
            bool flag = true;
            for(int k=0 ; k<n ; k++) {
                if(col[k]!=-1 && (col[k]-k==startRow-j || col[k]+k==startRow+j)) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                col[j]=startRow;
                dfs(startRow+1);
                col[j]=-1;
            }
        }
    }
}

int main() {
    for(int & i : col) i=-1;

    std::cin >> n;
    dfs(0);
    std::cout << count ;
}

• 코멘트
  
  상당한 well-known 문제이다. 처음 풀 땐 몰라서 찾아보면서 풀었던 것 같은데(약 1년전), 다 까먹었다가 지금 와서 다시 푸니 자연스럽게 그 방법으로 푼 것 같아서 다행이다.
  
  머릿속으로 퀸을 하나씩 놓다 보면, 자연스럽게 각 행(또는 열)마다 하나씩 놓아가면서 경우를 찾게 된다.
  대각선 규칙이 없다면 n!개의 경우가 나오겠지만, 대각선을 고려하면 경우의 수가 확 줄어들게 된다. 코드의 재귀함수 dfs()에서 각종 if문이나 flag를 빼면 n!이 나오게 될 것이다.
  코드의 흐름은 다음과 같다.
  1. n개의 행을 하나씩 채워 가면서 col[]배열에 채운 퀸의 열 번호를 저장한다. (가장 바깥쪽 재귀)
  2. 다음 행에 퀸을 놓을 때 n개의 열을 하나씩 체크해 보면서 (바깥쪽 for문)
  3. col[]배열의 기록을 싹 훑어보면서 그 열이 놓을 수 있는 열인지 확인한다 (안쪽 for문).

조금 더 세심하게 for문을 짜면 시간 복잡도는 더 줄어들겠지만 어차피 asymptotic한 관점에서는 변하지 않을 것이다.