9663

백준 9663번

Link: 9663번: N-Queen

---

문제 설명

많이들 알고있는 그 n-queen problem 문제다.

백트래킹 알고리즘의 교과서같은 문제로, 그냥 DFS 다돌리면 시간 부족해서 안풀릴 문제다.

짜다가 위키에 있는 소스코드를 봤는데, 내것보단 이게 훨씬 나아보여서 이걸 보고 이해하는 방향으로 했다.

내가 생각했던 것과의 가장 큰 차이점은 체스판을 1차원 배열로만 표현했다는 점.

1차원 배열로만 표현한 덕분에 2차원 배열을 순회하는 데 필요한 2중 for문을 단순 1중 for문으로 끝낼 수 있다는 시간적 이점이 있다.

대각선으로 다른 퀸이 있는지 검사하는 방법을 제일 이해하기 힘들었는데, 우선 지금까지 놓여진 퀸들에 대해 for문을 통해 검사한다.

이 for문의 iter 값은 곧 i번째 행 j번째 열에 퀸이 있는지를 표현하는 것이더라.

abs(count - j) == abs(i - map[j])는 count번째 행 i열의 대각 2방향(위쪽, 아래쪽 모두)에 퀸이 있는지 없는지 검사하는 내용이다.

이 if문에 걸리지 않았다면 퀸을 놓을 수 있는 것이므로 결과값을 1 증가시킨다.

만약 걸렸다면 즉시 for문을 나가고 바깥쪽 for문을 통해 다음 놓을 수 있는 자리를 찾는다.

이런식으로 반복하며 답을 찾는 문제다.

어제만해도 DFS문제에 대해 자신감이 좀 생겼는데 이 문제는 또 다른것 같다.

체스판을 1차원 배열로 표현하고 대각선방향 검사하는 코드만 봐도 아직 많이 모자라다는 걸 알 수 있었다.

---

정답 코드

//
// Created by Keith_Lee on 10/02/2019.
//

#include <iostream>
#include <stdlib.h>

using namespace std;

int N;
int map[14];
int result = 0;

void DFS(int count){
    if(count == N){
        result++;
        return;
    }

    for(int i=0; i<N; i++){
        bool available = true;

        for(int j=0; j<count; j++){ // 지금까지 놓아진 퀸들을 검사한다.
            if(map[j] == i || abs(count - j) == abs(i - map[j])){
                // map[j] == i: 새로운 퀸을 놓으려는 줄에 이미 다른 퀸이 있다.
                // abs(count - j) == abs(i - map[j]): 새로운 퀸을 놓으려는 위치의 대각선 방향에 이미 다른 퀸이 있다.
                available = false;
                break;
            }
        }

        if(available){
            map[count] = i;
            // count열 i행에 퀸을 배치한다.
            DFS(count+1);
        }
    }
}

int main(){
    cin >> N;

    DFS(0);

    cout << result << '\n';

    return 0;
}

---