[백준] 9663번 N-Queen

백준_9663

N-Queen은 전형적인 백트래킹 문제다

백트래킹(BackTracking)이란?

DFS와 동일한 구조의 코드를 쓰지만 차이점이 있다
DFS는 깊이가 깊어지는 방향으로 모든 노드를 탐색하지만, 백트래킹은 지금 노드가 답이 아니라고 생각된다면(=유망하지 않다면=promising하지 않다면) 그 방향으로 가지 않고 뒤로 돌아온다(=가지치기한다=prunning한다)

내용이 이해가 잘 되지 않는다면 코드를 보면 이해가 더 쉬울 것이다

답안 코드

n = int(input())
answer = 0
row = [0]*n
#row[x]=y : x행, y열에 퀸을 두겠다는 의미로 사용 가능하므로 2차원 배열이 필요 없음

def pomisingCheck(x):
    #체스판의 위에서부터 아래로 퀸을 두기 시작했으므로
    #현재 위치의 윗부분만 확인하면 된다
    for i in range(x):
        #현재 위치의 윗 부분에
        #같은 행에 둔 퀸이 있거나 or 왼/오 대각선에 둔 퀸이 있거나
        if row[x]==row[i] or abs(row[x]-row[i])==(x-i):
            return False
    return True

def dfs(x):
    global answer
    if x==n:
        answer += 1
        return
    
    #0~n-1열까지 모두 확인
    for i in range(n):
        row[x] = i  #x행, i열에 퀸을 둔다
        if pomisingCheck(x):
            dfs(x+1)

dfs(0)
print(answer)

Python3은 시간초과, PyPy3는 성공