[백준] [백트래킹] N-Queen 9663 (파이썬)

문제 접근

• 처음 보는 유형이 었고 공부를 해도 잘 몰라서 유투브 '코드랩' 님의 백트래킹 강의를 참조하였다
• 백트래킹 기본 개념
• 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 백트래킹

[알고리즘] 백트래킹

코드

# N - Queen
# 참조 코딩랩
import sys
input = sys.stdin.readline

def queen(row, col):
    
    for i in range(row):
        # 직선 겹칩
        # 행겹침, 열겹침
        if row == v[i][0] or col == v[i][1]:
        #if row == vx[i] or col == vy[i]:
            return 0
        # 대각선 겹침
        if abs(v[i][0]- row) == abs(v[i][1] - col):
        #if abs(row - vx[i] == abs(col - vy[i])):
            return 0

    # 나는 row 번째 행에서 체스 말을 (row,col)에 놓았다
    v[row][0] = row
    v[row][1] = col

    # 종료조건
    if row == n-1:
        # 행이 마지막에 간다면 탐색완료
        # print(v) 행에서 퀸이 놓인 위치를 알고 싶다면 이부분에서 프린트하면 된다.
        return 1

    result = 0
    for j in range(n):
        result += queen(row + 1, j) # 행을 증가시켜서 그다음 행을 탐색한다.
        
    return result


n = int(input())
v = [ [0,0] for _ in range(n) ]

answer = 0
for i in range(n):
   answer += queen(0,i) # 0행 i열마다 DFS를 실행한 결과값들 즉 n queen을 만족하는 경우의수
print(answer)