N-Queen

BOJ 'N-Queen' 문제 보러가기

풀이코드

처음으로 풀이한 코드를 제출했을 때는 시간 초과가 발생했다. 구글링 해보니 이중 배열 사용이 가장 큰 문제였던 듯 하다.
최종적으로 제출해서 성공한 코드는 아래와 같다.

#include <iostream>
using namespace std;

int N, answer =0;
int board[20]; // index y 의 x위치 = board[y]

bool checkAvailable(int y,int x){
    for(int i=0;i<y;i++){
        // 같은 행과 열에 있거나 대각선에 있는 경우
        if(board[i] == x || abs((x - board[i])) == y-i){
            return false;
        }
    }
    return true;
}

void dfs(int depth){
    // 2-1. 놓은 Queen의 개수가 총 N개가 되면 답을 증가하고 재귀 종료한
    if(depth == N){
        answer++;
        return;
    }
    
    for(int i =0; i<N;i++){
        // 2-2. board의 depth행 i열에 Queen을 놓을 수 있는지 판별
        if(checkAvailable(depth, i) == true){
            // 가능하면 Queen을 놓는다.
            board[depth] = i;
            dfs(depth+1);
        }
    }
    // 2-3. 한 행의 모든 열을 시도하고 나면 자동으로 함수 종료
    return;

}

int main() {
    // 1. 입력받기
    cin >> N;

    // 2. DFS로 가능한 경우의 수 탐색하기
    dfs(0);
    
    // 3. 최종 정답을 출력하기
    cout << answer;
}

스스로 풀이하지 못한 이유

1. 이번에는 가독성도 신경쓴 코드를 짜보려 메소드를 분리하면서 코드를 작성하였다. N이 작아서 시간 복잡도는 크게 신경쓰고 있지 않았는데, 그러다보니 메소드 호출문을 종합해보면 3중 for문까지 나온다는 것을 눈치채지 못했다.
2. 체스 룰을 몰라서 검색을 통해 Queen이 모든 방향으로 움직일 수 있다는 것은 알아냈지만 한 행당 한 개의 퀸만 존재할 수 있다는 것을 알지 못했다. 이것으로 인해 더 효율적인 풀이를 생각해내지 못하고 N*N 배열을 만들게 된 듯 하다 ㅠ.ㅠ

참고 자료

• [백준 / BOJ] - 9663번 N-QUEEN C++ 풀이