[백준] 9663번 : N-Queen (python 파이썬)

👉 9663번 : N-Queen

---

✍ 내 코드

---

# 골드 5레벨        N-Queen
from collections import defaultdict

N = int(input())

cnt = 0
cen = defaultdict(int)
l = defaultdict(int)
r = defaultdict(int)


def re(idx):
    global cnt
    if idx == N:
        cnt += 1
        return

    for i in range(N):
        if not cen[i] and not l[i + idx] and not r[i - idx]:
            cen[i] = 1
            l[i + idx] = 1
            r[i - idx] = 1
            re(idx + 1)
            cen[i] = 0
            l[i + idx] = 0
            r[i - idx] = 0
    return


re(0)
print(cnt)

---

✍ 팁

해당 문제는 백준과 프로그래머스 둘다 존재하는 문제인데 백준의 특성상 python의 시간복잡도가 매우 타이트하여 다른 분들의 프로그래머스 통과 코드가 백준의 python, pypy3에서도 시간초과가 걸리는 경우가 많다.

내 코드는 pypy3에서 통과한 코드이며 python에서는 시간초과에 걸린코드이다.
아마 재귀 함수를 부르는 부분에서 시간을 많이 먹는 것 같은데 pypy3에서 통과를 한다면 대부분 로직이 틀린 코드는 아니니 걱정할 필요 없다.

• 시간초과를 해결하기 위해 list 안에 채택된 idx행을 in 으로 체크하는게아닌
  O(1)의 시간밖에 안걸리는 딕셔너리를 이용하여 시간초과를 해결했다.
  파이써닉한 코드를 위해 defaultdict를 이용했으니 궁금한 사람은 찾아보면 좋다.
• cen은 일직선상의 겹치는 부분 대각선 좌, 우는 현재 행의 깊이만큼더해줘 겹치는지를 체크