[백준 9663번] N-Queen - python

문제 링크

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

9663번: N-Queen

 

풀이 

- dfs 사용한 백트래킹 문제 

graph는 index 번호가 row 값, 저장된 값이 col 값으로 표현한다. 

따라서 맨 윗줄 왼쪽부터 퀸을 하나씩 놓고, 어차피 맨 위에서부터 하나씩 놓기 때문에 위에 놓인 퀸들에 대해서 놓을 수 있는지 없는지 검사한다. 

같은 열에 퀸이 있거나, 대각선에 퀸이 위치하면 안된다. 

대각선의 퀸이 위치한 것은 row 의 차이와 col 의 차이가 같은 것으로 판단할 수 있다. 

import sys
input = sys.stdin.readline 

def dfs(depth):
    global count 
    # n개 다 놓았으면 개수 증가 
    if depth == n:
        count += 1 
    else :
        for i in range(n):
            # 퀸 놓기 
            graph[depth] = i
            
            result = True
            # 위에 놓여있는 퀸들이랑 비교 
            for j in range(depth):
                # 같은 열에 위치하거나 대각선에 위치하면 놓을 수 없음 
                if graph[depth] == graph[j] or abs(graph[depth] - graph[j]) == depth-j:
                    result= False
                    break
                    
            # 놓을 수 있으면 
            if result :
                dfs(depth+1)
 
n = int(input())
count = 0   
# (인덱스 번호, 값)
graph = [0] * n
dfs(0)
print(count)