[백준][C++] 9663번: N-Queen <190>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

9663번: N-Queen

 

생각의 흐름

우선 이번 문제를 스스로 다 해결하지 못해 아쉬움이 남는다... 정리라도 잘 해두어야 겠다.

 

Queen은 가로, 세로, 대각선으로 이동이 가능하다. 이 문제는 이러한 Queen을 배치시킬 수 있는 총 경우의 수를 구해야 한다.

또한 Back Tracking 알고리즘을 적용해야한다. 탐색을 진행하다가, 더이상 답이 나올수 없는 case에 도달한다면 return 하면 된다.

 

우선 생각을 편하게 하기 위해 N=4 인 경우일때 생각해 보자.

각 행을 level 이라 부를것 이다. 위 4x4 행렬은 총 level 3 까지 있다. 위 배열을 표현하기 위해 2차원 배열을 사용하지 않을 것 이다.

 

우리는 2차원 배열이 아닌, Arr이라는 1차원 배열로 표현할 것 이다. 다음 그림을 살펴보자.

Arr[i] = j 는 i번 말이 (i level, j 번째 위치)에 놓였음을 의미한다.

 

위 그림을 반영 한다면 다음과 같은 배열이 될것 이다.

전체적인 알고리즘의 흐름은 다음과 같아진다.

int arr[N+1];

void nQueen ( int level ) {
    if(level == N){
        // 카운트 해주고 종료
        return;
    }

    for(int i = 0; i < N; i++){
        arr[level] = i;
        if(isValidPosition(level)){ // 타당한 위치라면
            nQueen(level + 1); // 그다음으로 재귀 진행
        }
    }
}

level 0의 4 위치에 한번씩 queen을 배치 해 본 후, 다음 level 2로 이동하여 이전 퀸과 겹치지 않도록 배치하는 흐름이다.

일단 대략적 흐름만 보고, 다음 글을 마저 읽어달라!

---

그림에서 level 2를 채워야 하는 순간이라고 생각해 보자, 이미 level 0에는 2가, level 1에는 0이 저장되어 있다.

level 2에 숫자 3을 선택했다. 그림은 다음과 같다.

level 1의 queen은 level 0의 queen과 충돌이 발생하지 않기 때문에 level 1에 0이라는 값으로 queen이 들어 간 것 이다.

=> 따라서 현재 level 앞에 있는 칸에 저장된 queen들은 서로간에 충돌이 발생하지 않음을 보장한다.

 

level 2에 추가될 queen만 이전에 놓인 다른 queen들과 비교하는것으로 충분 하다.

---

그럼 level 2에 Queen을 배치할 때는, 이전 queen들과 어떠한 방식으로 비교할까? 다음 그림을 살펴보자.

 

1) 두 퀸은 같은 열에 있으면 안된다.

이는 다음과 같이 간단하게 해결할 수 있다.

bool isValidPosition(int level){
    for(int i = 0; i < level; i++){
        if(arr[level] == arr[i]){
            return false;
        }
        // 생략
    }
    return true;
}

arr[level] == arr[i]인 경우 같은 행에 Queen이 배치 된 것 이다. 이때는 바로 false를 반환해주면 된다.

 

2) 두 퀸은 대각선 상에 있으면 안된다.

두 퀸은 대각선에 있다는 말은, 각 지점 간의 level 차이와 열번호 차이가 동일할 경우 대각선 상에 위치한다는 의미이다.

이는 말보다 위 그림을 보면 이해하기 수월하다.

 

이를 코드로 완성시키면 다음과 같다.

bool isValidPosition(int level){
    for(int i = 0; i < level; i++){
        if(arr[level] == arr[i]){
            return false;
        }else if(level - i == abs(arr[level] - arr[i])){
            return false;
        }
    }
    return true;
}

 

한가지 의문?

직전의 식을 보면 cols 간의 차를 구할때는 절대값을 사용하였는데, level - i 에는 절대값을 사용하지 않았다?

왜 그런 것 일까?

 

이는 우리의 isValidPosition() 메서드를 보면 i가 0부터 level 전까지만 확인해보기 때문이다.

즉, i는 항상 level 보다 작기 때문이다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 16

int N, cnt;
int arr[MAX];

bool isValidPosition(int level){
    for(int i = 0; i < level; i++){
        if(arr[level] == arr[i]){
            return false;
        }else if(level - i == abs(arr[level] - arr[i])){
            return false;
        }
    }
    return true;
}

void nQueen(int level){
    if(level == N){
        cnt++;
        return;
    }

    for(int i = 0; i < N; i++){
        arr[level] = i;
        if(isValidPosition(level)){
            nQueen(level + 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    nQueen(0);
    cout << cnt;

    return 0;
}