백준 9663 <N-Queen> Python

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

9663번: N-Queen

---

전형적인 백트래킹 문제입니다. 다만 조건 시간이 빡빡해 운이 안좋으면 실패, 운이 좋으면 통과라는 어이없는 결과가 나오기도 하는 문제입니다. 저의 경우에는 is_empty 함수의 if queen[row] == queen[i] 조건문이 원래 if queen[i] == queen[row] 였는데 순서를 바꾸어주자 넉넉하게 통과하기도 했습니다. 정확한 이유는 모르겠지만 코드가 맞고 다른 이들과의 코드와 차이를 잘 모르겠다면 이런 저런 시도를 다 해보시면 좋을 것 같습니다.

---

import sys

# 인덱스에 배치 가능한지 판단하는 함수

def is_empty(row):

    # 가로는 할 필요 없음

    # 세로, 대각선

    for i in range(row):

        if queen[row] == queen[i] or abs(queen[i] - queen[row]) == abs(i - row):

            return False

    return True

# NQueen 재귀 함수

def n_queen(row):

    # 마지막 인덱스를 넘어가면

    if row == N:

        global cnt

        cnt += 1

        return

    else:

        # 인덱스를 돌며 탐색

        for i in range(N):

            # 인덱스에 퀸 배치

            queen[row] = i

            # 인덱스에 배치 가능하면

            if is_empty(row):

                # 재귀 호출

                n_queen(row+1)

N = int(sys.stdin.readline())

# 카운트

cnt = 0

# 퀸 인덱스

queen = [0] * N

# 함수 호출

n_queen(0)

print(cnt)