백준 9663번 파이썬 문제풀이(N-Queen)

---

N-Queen은 dfs에서 너무나 유명한 문제이므로 풀이 과정은 생략하겠다. 단, 해당 문제 시간초과코드와 통과코드가 2개있다. 둘다 존재하는데 거의 비슷한 코드인데 시간초과나는 이유를 모르겠다. 아마 in연산자가 매번 반복문을돌면서 비교하는 연산보다 더 빠르게 수행되기 때문인거 같다. 2개의 코드 모두 올려놓겠다.

1. 통과코드

def checking(r, c):
    for j in range(len(check)):
        if abs(j - r) == abs(check[j] - c):
            return False
    return True


def dfs(r):
    global count

    if r == N:
        count += 1
        return

    for col in range(N):
        if col not in check:
            if checking(r, col):
                check.append(col)
                dfs(r + 1)
                check.pop()


N = int(input())

check = []
count = 0


dfs(0)
print(count)

 

2.시간 초과 코드

def checking(r, c):
    for j in range(r):
        if check[j] == c or abs(j - r) == abs(check[j] - c):
            return False
    return True


def dfs(r):
    global count

    if r == N:
        count += 1
        return

    for col in range(N):
        if checking(r, col):
            check[r] = col
            dfs(r + 1)


N = int(input())

check = [0] * N
count = 0


dfs(0)
print(count)