[백준/C++] 9663번 N-Queen 풀이

문제 설명

---

 

---

문제 풀이

---

 

처음 시도에는 N이 15밖에 되지 않으므로 브루트포스가 당연한 것은 알고 있었고 2차원 배열로 가로 세로 대각선에 있는 값을 true로 변경하며 dfs(재귀)로 풀어나가려고 했으나 코드를 작성하다보니 가로 세로 대각선의 값을 계속 변경하는 불편함이 있고 굳이 2차원으로 풀어나가는 비효율성을 유지할 필요가 없다고 느끼게 되었다.

 

이후 바로 가로배열, 세로배열을 생성하였고 대각선 값을 어떻게 변경할까 고민하게 되었다. 과거 수업에서 배운 자료를 참고하였고 / 방향 대각선은 현재 행과 열의 합이 같다는 것과 열과 행 중 하나의 값만 뒤에서부터 값을 세어보면 \ 방향 대각선도 해결되는 것을 알게 되었다.

위 그림과 같이 row와 col의 합이 대각선의 값임을 알 수 있다.

---

코   드

---

#include <bits/stdc++.h>
using namespace std;
int N, answer;
bool rows[16], cols[16], back_cross[32], cross[32];

void set_queen(int depth) {
    if (depth == N) {
        answer++;
        return;
    }

    for (int col = 0; col < N; col++) {
        if (!rows[depth] && !cols[col] && !cross[depth + col] && !back_cross[N - depth + col]) {
            rows[depth] = 1, cols[col] = 1, cross[depth + col] = 1, back_cross[N - depth + col] = 1;
            set_queen(depth+1);
            rows[depth] = 0, cols[col] = 0, cross[depth + col] = 0, back_cross[N - depth + col] = 0;
        }
    }

    return;
}

int main() {
    cin >> N;
    set_queen(0);
    cout << answer;
}

---

느낀점:

사실 학교에서 이산수학을 배울 때 Z3 SMT Solver를 통해 논리식으로 N-Queen problem을 해결한 적이 있었지만, 그 때 같은 대각선에 있는 것을 처리하는 방법을 고민하지 않고 힌트로 얻어서 그런지 너무나 어려웠다.

대충 저렇게 몇개의 논리식을 true false로 풀어나가게 한다면 c나 c++로도 빠르게 가능할까? 라는 궁금증이 생겼다.

링크: https://www.acmicpc.net/problem/9663

9663번: N-Queen