N-queen [백준 9663]

1. 문제 접근 방법

- DFS를 기본적으로 활용하는 문제이다.

-> DFS를 활용하되, 각각의 행마다 열을 하나씩 선택해주면 된다.

-> 이 때, 열을 중복해서 선택하지 않고, 또한, 기존에 선택한 점들과

    대각선에 존재하지 않도록 하면서 선택하면 되는 문제이다. 

-> 이렇게 해서 row가 N+1에 도달했을 때, 정답의 개수를 1 증가시키면 되는 문제이다.  

 

 

2. 코드

N = int(input())


ans = 0 


def check(row, col, checked, N):
    
    for x, y in checked:
        if abs(x-row) == abs(y-col):
            return False
            
    return True
    
    
    
    



def dfs(row, cols, checked, N):
    
    global ans 
    
    if row == N+1:
        ans += 1 
        return 
    
    
    
    for i in range(1, N+1):
        if cols[i] == False and check(row, i, checked, N):
            cols[i] = True
            checked.append((row, i))
            dfs(row+1, cols, checked, N)
            checked.pop(len(checked)-1)
            cols[i] = False
    
    
  

cols = [False]*(N+1)
checked = []

dfs(1, cols, checked, N)


print(ans)