문제

N-Queen

정답 코드

Python

import sys


def is_promising(x):
    global g
    for i in range(x):
        if g[i] == g[x] or abs(g[i] - g[x]) == abs(x - i):
            return False
    return True


def n_queen(x):
    global ans
    if x == n:
        ans += 1
        return
    for i in range(n):
        global g
        g[x] = i
        if is_promising(x):
            n_queen(x + 1)


n = int(sys.stdin.readline().rstrip())
ans = 0
g = [0 for _ in range(n)]
n_queen(0)
print(ans)

C++

#include <bits/stdc++.h>
using namespace std;
int n, g[16], ans;
bool isPromising(int x) {
    for (int i = 0; i < x; i++) {
        if (g[x] == g[i] || abs(g[x] - g[i]) == abs(x - i)){
            return false;
        }
    }
    return true;
}

void nQueen(int x) {
    if (x == n) {
        ans += 1;
        return;
    }
    for (int i = 0; i < n; i++) {
        g[x] = i;
        if (isPromising(x)) {
            nQueen(x + 1);
        }
    }
}

int main() {
    cin >> n;
    nQueen(0);
    cout << ans;
    return 0;
}

풀이

전형적인 백트래킹 문제입니다.
체스에서 퀸이 이동할 수 있는 경우의 수를 생각하면서 서로서로 잡아먹히지 않게 퀸을 놔야 하는 문제인데요
난이도가 개인적으로 어려웠던 이유는 시간복잡도 때문입니다...

이게 처음 풀 때는 아무 생각 없이 2차원 배열을 만든 후 해당 배열을 전달하면서 풀려고 시도했는데...

매우 비효율적으로 구성해서 그런지 정답은 나오지만 무조건 시간초과가 뜨더라구요...
그래서 이건 못 풀것 같다...!! 라는 생각이 들어서 다른 사람의 발상을 가져와야겠다고 생각했습니다...
어차피 더 고민해도 의미가 없을 것 같아서
그러다가 이 블로그 를 참고해서 결국 풀었습니다

각 퀸이 놓인 자리를 2차원 배열 말고 1차원 배열로 놓을 수 있다는 발상이 와...
문제를 많이 풀면 나오는 센스 같더라구요

하지만 저는 여기서 한 번 더 틀렸습니다

import sys
cnt = 0
row = []


def is_promising(x):
    global row
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return False
    return True


def n_queen(x, n):
    global cnt
    if x == n:
        cnt += 1
        return
    for i in range(n):
        global row
        row[x] = i
        if is_promising(x):
            n_queen(x + 1, n)


def solution():
    global row, cnt
    n = int(sys.stdin.readline().rstrip())
    row = [0 for _ in range(n)]
    n_queen(0, n)
    print(cnt)


if __name__ == "__main__":
    solution()

위 코드로 제출했더니 틀렸다고 뜨더라고요

그래서 문제가 뭘까?? 라고 생각을 했더니 불필요하게 문제를 함수화 시켜서 푼 것 같아서(프로그래머스 스타일) 전부 밖으로 빼고 위의 코드로 제출했더니...!!
드디어 통과했습니다

그리고 궁금해서 같은 로직으로 C++로도 풀어봤는데 시간이 이렇게 나오더라구요

역시 파이썬이 많이 느리긴 한가 봅니다

---

근데 혹시 몰라서 아까 틀린 코드로 제출하니깐

오잉??
이번에는 통과했습니다
운이 좋으면 통과하는 것 같은데 그래도 확실하게 하려면 느린 파이썬에서는 불필요한 함수를 제거하면서 알고리즘을 풀어야 할 것 같네요