[파이썬]백준 9663 N-Queen

링크

백준 9663 N-Queen

싸피에서 모의 A형을 보고 벽을 쎄게 느꼈다.
잘 이해가 안돼 미뤄두고만 있던 백트래킹에 대한 연습의지를 다시 불태우게 만들었다.
N-Queen 문제는 백트래킹의 아주 유명한 문제인데 미루고 미루다가 드디어 풀었다.

로직도 맞고 가지치기도 제대로 했다고 생각했으나 파이썬으론 시간초과가 떠 pypy로 돌리니 풀렸다.

알아보니 백준에서 백트래킹 문제(해당 문제를 포함하여)는 파이썬으로 통과가 안되는 경우가 많다는 것을 알았다.
파이썬으로 통과한 사람들 코드를 보니 체스판을 대각선으로 잘랐을 때 퀸이 대칭을 이룬다는 점을 이용했는데 이러한 지식이 없다면 풀 수가 없는 것 같다.

다른 언어를 배워야할 필요성이 점점 늘어난다.

정답 코드

def check(r, c):
    for row in range(r):
        if c == board[row]:
            return False
        if r - c == row - board[row]:
            return False
        if r + c == row + board[row]:
            return False
    return True

def bt(idx):
    global ans

    if idx == N:
        ans += 1

    else:
        for i in range(N):
            if check(idx, i):
                board[idx] = i
                bt(idx + 1)
                board[idx] = 0


N = int(input())
board = [0] * N
ans = 0

bt(0)
print(ans)

알게된 것👨‍💻

• dfs와 백트래킹은 아주 약간의 차이만 있다.
• 다른 언어도 배워야 겠다.