[백준] 9663번 : N-Queen

문제

 

---

풀이

 

N-Queen 문제는 백트래킹의 대표적인 문제이다. 근데 난 얘가 너무 어렵다...

이런 체스판에 퀸을 놓고 이 퀸들이 서로 공격할 수 없게 놓는 문제이다.

퀸은 가로세로대각선으로 이동할 수 있으니 어떠한 퀸들도 같은 행열대각선에 위치하지 않도록 배치해야 한다.

---

소스코드

 

#include <iostream>

using namespace std;
const int SIZE = 15;

int n, ans;
int check[SIZE];

bool promising(int num) {
    int idx = 0;
    while (idx < num) { //이미 놓여있는 모든 퀸에 대해
        if (check[num] == check[idx] || abs(check[num] - check[idx]) == (num - idx)) //같은 행, 같은 대각선 체크
            return false;
        idx++;
    }
    return true;
}

void backtracking(int cnt) {
    if (cnt == n) { //기저 조건
        ans++;
        return;
    }
    for (int i = 0; i < n; i++) {
        check[cnt] = i; //i행 cnt열에 퀸 배치
        if (promising(cnt))
            backtracking(cnt + 1);
    }
}

/**
 * 4368ms
 */
int main() {
    //입력
    cin >> n;

    //연산
    backtracking(0);

    //출력
    cout << ans << '\n';
}

사실 이 문제를 푼지 오래돼서 기억이 가물가물하지만 설명을 해보겠다.

 

int n, ans;
int check[SIZE];

tot_cnt는 전체 경우의 수를 담을 int 변수이다.

처음엔 체스판 자체를 구현하고자 해서 visited를 2차원 bool 배열로 했더니 시간초과가 됐다.

그래서 잘 생각해보니 굳이 2차원 배열을 구현할 필요가 없었다.

 

어쩌다보니 아이콘이 폰이지만 아무튼...

두개 이상의 퀸이 같은 열에 있는 것은 불가능하다. 그렇기 때문에 visited 배열을 int로 선언하고, 그 값에 퀸의 행을 저장하면 1차원 배열로도 행과 열을 모두 표현할 수 있다.

예를 들어 visited[1] = 2라면 퀸 하나가 1열 2행에 있다는 뜻이 되는 것이다.

 

void backtracking(int cnt) {
    if (cnt == n) { //기저 조건
        ans++;
        return;
    }
    for (int i = 0; i < n; i++) {
        check[cnt] = i; //i행 cnt열에 퀸 배치
        if (promising(cnt))
            backtracking(cnt + 1);
    }
}

그리고 일단 promising 함수 전에 queens 함수부터 보자.

종료 조건은 굳이 설명이 필요없을 것 같고, 행을 하나씩 옆으로 이동하며(cnt +1) 특정 열(i)에 퀸을 배치해본다.

이제 내가 방금 배치한 이 퀸이 이전까지 배치된 퀸을 공격하지 않는지 확인하기 위해 promising 함수를 사용한다.

만약 적절한 위치라면 이를 적용하고 다음 행에 퀸을 배치하기 위해 queens(cnt + 1)을 호출한다.

그렇다면 promising 함수에선 어떻게 이 퀸의 위치가 적절한지 확인할까?

 

bool promising(int num) {
    int idx = 0;
    while (idx < num) { //이미 놓여있는 모든 퀸에 대해
        if (check[num] == check[idx] || abs(check[num] - check[idx]) == (num - idx)) //같은 행, 같은 대각선 체크
            return false;
        idx++;
    }
    return true;
}

index가 나타내는 즉 visited[index]는 이번에 새로 배치한 퀸이 된다. 1행부터 index행 직전까지 while문을 돌며 새로운 퀸이 이전의 퀸들을 공격할 가능성이 있는지 살펴본다.

visited[index] == visited[k]라면 두 퀸의 열이 동일하다는 뜻이고, abs(visited[index] - visited[k]) == (index - k) 그러니까 두 퀸의 행과 열의 차이가 동일하다는 것은 두 퀸이 같은 대각선에 위치한다는 뜻이다.

이렇게 모든 퀸을 확인하는 동안 문제가 없었다면 true를 반환한다.

 

붉은색 퀸(그림에선 폰)을 이번에 새로 배치한 visited[index]라고 하면

while문을 돌며 푸른색 퀸(visited[k])와 위치관계를 확인해보는 것이다.