[Python]백준 9663번/N-Queen/백트래킹

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

9663번: N-Queen

⚡️ 문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제

퀸을 놓는 방법의 수를 구하는 프로그램

⚡️ 해결 방법

퀸이 서로 공격할 수 없도록 하는 방법

1. 같은 행에 위치하면 안됨

2. 같은 열에 위치하면 안됨

3. 대각선상에 위치하면 안됨

 

graph_col 은 X행에서 퀸이 놓인 열의 위치를 저장할 것이다.

queen을 놓은 뒤 이 queen의 자리가 promising 한지 확인해야한다.

이를 확인하는 함수가 promising 함수이다.

이 방식으로 하면 같은 행에 위치할 queen은 없기 때문에 같은 행인지 체크는 하지 않아도 된다.

나머지 같은 열에 위치하는지 graph_col[before_row] == graph_col[row]

대각선상에 위치하는지 abs(graph_col[before_row]-graph_col[row])==abs(before_row-row))

확인한다.

 

⚡️ 코드

import sys
input = sys.stdin.readline

n = int(input())

def promising(row):
    for before_row in range(row):
        # 같은 열 or 같은 대각선 상에 있는 경우
        if(graph_col[before_row] == graph_col[row] or 
           abs(graph_col[before_row]-graph_col[row])==abs(before_row-row)):
            return False
    return True

result = 0
graph_col = [0] * n 
def dfs(row):
    global result
    if row == n:
        result += 1
    else:
        for i in range(n):
            # Queen 놓기
            graph_col[row] = i
            if promising(row):
                dfs(row+1)

dfs(0)
print(result)