🟩 [백준] [Python] [Gold4] 9663번_N-Queen

문제

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

9663번: N-Queen

풀이

# 백준 9663번 문제 - N-Queen
import sys
input = sys.stdin.readline
n = int(input().rstrip())
answer = 0
row = [0] * n

def is_promising(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i):
            return False
    return True
def n_queens(x):
    global answer
    if x == n:
        answer += 1
    else:
        for i in range(n):
            row[x] = i
            if is_promising(x):
                n_queens(x+1)
n_queens(0)
print(answer)

이 방식으로 풀면 시간초과가 발생해서 pypy3로 제출해야 한다. 

그래서 visited를 만들어서 제출했는데도 시간초과이다.. 

import sys
input = sys.stdin.readline

def check(x):
    for i in range(x):
        if rows[x] == rows[i] or abs(rows[x] - rows[i]) == x - i:
            return False
    return True

def dfs(x):
    global cnt

    if x == n:
        cnt += 1
        return

    for i in range(n):
        if visited[i]: 
            continue

        rows[x] = i
        if check(x):
            visited[i] = True
            dfs(x+1)
            visited[i] = False

n = int(input())
rows = [0] * n
visited = [False] * n
cnt = 0

dfs(0)
print(cnt)

백트래킹 문제는 처음이어서 이해하는데 너무 어려운 문제였다.