BOJ_9663 N-Queen

• TOC {:toc}

이 글은 백준 온라인 저지의 9663번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.21 (Python)

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

def dfs(x):
    global result
    if x == N:
        result += 1

    else:
        for i in range(N):
            row[x] = i
            if adjacent(x):
                dfs(x + 1)

N = int(input())
row = [0] * N
result = 0
dfs(0)
print(result)

아이디어 & 풀이

백 트래킹의 대표적인 예시인 N Queen 문제이다.

• dfs를 이용해 각 열을 탐색하면서 더는 queen을 놓을 수 없으면 drop 한다.
• N Queen과 백 트래킹에 대한 자세한 내용은 [[wiki0:fc-algo-algorithm-21-back-tracking]]{강의 정리글}을 참고하면 된다.

디버그

• 작성했더니 시간초과가 나서 dfs를 queue 이용해서 구현하다가 포기했다. 훨씬 복잡해지기만 하는 듯.
• 관련 글을 검색해봤더니 정석적으로 풀면 파이썬에서는 시간 내에 풀기 어려운 알고리즘인 것 같다. PyPy도 사소한 것에 따라 간당간당하게 통과하는듯하다.

피드백

2022.04.08 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim();

function main() {
    function isAvailable(x) {
        // iterate rows upper x
        for (let i = 0; i < x; i += 1) {
            if (row[i] === row[x] || Math.abs(row[x] - row[i]) === x - i) return false;
        }
        return true;
    }

    function dfs(x) {
        if (x === N) count += 1;
        else {
            for (let i = 0; i < N; i += 1) {
                // put queen at i, x
                row[x] = i;
                if (isAvailable(x)) dfs(x + 1);
            }
        }
    }

    // row[row] = col
    const row = Array(N);
    let count = 0;
    dfs(0);

    return count;
}

const N = parseInt(input);

console.log(main());

참고 답안 1

아이디어 & 풀이

참고 답안 2

print(
    [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596][int(input())]
)

아이디어 & 풀이

N에 따른 N Queen의 경우의 수를 리스트로 만들어서 N에 따라 출력한다.

• 수행 시간이 두 자리 ms 단위인 답안은 대부분 이 풀이이다.
• 세~네 자리 ms 단위인 답안도 대부분 N이 큰 경우는 답안을 직접 출력하고 넘어가 시간을 단축시킨 것이었다.
  • 아마 시간 때문에 통과가 안 되는 경우를 제외시키고 작성한 코드가 맞는지 확인하려고 한 것 같다.
• 알고리즘적으로는 의미가 없는 답안에 가깝지만 일단 작성.