[백준] 9663번 N-Queen (by Python)

문제

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

9663번: N-Queen

풀이

def n_queens(col, i):
    if (promising(col, i)):
        if i == n:
            global ans
            ans += 1
        else:
            for j in range(1, n + 1):
                col[i + 1] = j
                n_queens(col, i + 1)

def promising(col, i):
    k = 1
    flag = True
    while k < i and flag:
        if col[i] == col[k] or abs(col[i] - col[k]) == (i - k):
            flag = False
        k += 1
    return flag

n = int(input())
col = [0] * (n + 1)
ans = 0
n_queens(col, 0)
print(ans)

백트래킹 로직을 생각해내긴 했으나 효율적이고 깔끔하게 구현 코드를 짜진 못했다. 이 점이 못내 아쉬워 레퍼런스들을 참고해 짠 코드이다. 원래 접근방식은 체스판을 이중 리스트로 구현해 갈 수 없게 된 곳들을 모두 표시하는 방법이었는데, 이렇게 row마다 선택한 column을 담고 다니는 방법이 더 light하고 좋은 듯하다. 또한, 대각선을 체크하기 위해 col과 row 값의 차이를 이용하는 테크닉도 인상적이었다.

 

※ 그렇지만 우리의 파이썬은 이 코드로 시간초과를 벗어날 수 없다!!

 

이 문제 역시 내가 원하는 수준에서는 이 정도 로직을 구현했으면 충분하다고 생각이 들어 더 개선을 하는 데에 시간을 쓰진 않았다. 

그래도 맞았습니다! 를 받고 싶어 아래와 같은 코드를 이용했으니 혹시 같은 생각이신 분들은 참고하시길...😅

 

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