해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 9663 N-Queen - 백트래킹

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다.

2. 한 줄에 두 개 들어가는 게 불가능하기 때문에, 행과 열 중에 하나를 정해서 기준점 잡고 백트래킹에 들어갑니다.

3. 열을 기준점으로 잡은 경우에 col[x]에 행의 번호를 넣습니다. 이때, col[x]에 행의 번호를 넣었을 때, 다른 퀸이 공격할 수 있는지 check합니다. 퀸이 공격할 수 없는 위치라면, dfs(x+1)함수를 호출하여, 그 다음 열에 대해서 같은 작업을 반복합니다.

4. 재귀함수에서 전달인자의 크기가 N이면 결과값으로 카운팅 합니다.

전체 코드

def check(x):
    for i in range(x):
        if col[x] == col[i] or abs(col[i]-col[x]) == x-i:
            return False
    return True

def dfs(x):
    global res
    if x == n:
        res += 1
        return
    for i in range(n):
        col[x] = i
        if check(x):
            #print(x, " ", i)
            dfs(x+1)

n = int(input())
res = 0
col=[0]*15

dfs(0)
print(res)