[ BOJ 9663 ] N-Queen (Python)

문제

퀸은 상, 하, 좌, 우, 대각선으로 거리제약 없이 이동할 수 있다.

문제 풀이 (🔗 참고)

N x N 체스판에 N개의 퀸을 배치해야하므로 반드시 모든 행에 퀸이 들어가야 한다.
따라서 0열부터 N-1열까지 퀸을 놓는 방법을 for문으로 돌린다. (dfs)
이전 열에 겹치는 행이 있는지 체크해준다. (check)

1. (x,i) 에 퀸을 놓고, 이전 행과 겹치는지 체크해준다.
2. 겹치지 않으면 다음 행으로 이동한다.
3. n번째 행까지 이동하면, 겹치지 않게 퀸을 놓았다는 뜻이므로 cnt를 1 증가시켜준다.

• rows[x] == rows[i] : 같은 열에 놓아져있는지 확인
• abs(rows[x] - rows[i]) == x - i : 같은 대각선에 놓아져있는지 확인

코드

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
    else:
        for i in range(n):
            rows[x] = i
            # (x,i)에 퀸을 놓고, 이전 행과 겹치지 않는지 체크해줌
            if check(x):
                # 겹치지 않으면 다음 행으로 이동
                dfs(x+1)

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

dfs(0)
print(cnt)

시간 초과 🤔

• 위의 코드로 제출하면 시간 초과가 발생하는데.. 맞은 척 했나보다.
• 방문 체크를 해줘서 한번 방문한 곳은 다시 방문 안하도록 해주었다. (pypy로 제출!)

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)