[BOJ / 파이썬] 9663: N-Queen

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

단계 : 백트래킹

알고리즘 분류 : 브루트포스 알고리즘, 백트래킹 

 

풀이:

N - Queen은 유명한 문제로 알고 있다.

문제도 이해하기 쉬운데 체스판에 퀸들이 서로 공격하지 못하게 놓는 문제를 의미한다. 해당 문제에서는 N을 입력받아 N x N 체스판에 퀸들을 서로 공격하지 못하게 두는 방법들의 개수를 찾는 것이 목표이다.

 

퀸의 공격 경로는 가로, 세로, 대각선이므로 모든 퀸들이 서로 가로, 세로, 대각선에 겹치지 않게 두면 된다. 그러기 위해서는 퀸들의 전체 위치를 파악할 수 있어야 하며 퀸을 어떤 자리에 놓으려고 할 때 다른 퀸들과 겹치지 않는지 확인할 수 있어야 한다. 

 

해당 문제는 퀸을 놓을 수 있는 방법의 수를 구하는 문제이므로 백트래킹을 통해 모든 경우의 수를 찾아본다.

 

퀸의 위치를 2차원 배열을 통해 저장해도 되겠지만 그것보다는 1차원 배열을 통해 퀸의 위치를 저장해보도록 하겠다.  visited[n]의 값이 i라고 할 때 이는 n행 i열에 퀸이 있다는 의미이다. 즉 visited[1]의 값이 3라고 할 경우 이가 의미하는 것은 1행 3열의 위치에 퀸이 있는것이다. 

 

이를 이용하여 생각해보면 가로, 세로, 대각선을 확인하는 check함수를 짤 수 있다.  visited의 인덱스가 행을 의미하므로 같은 행에는 퀸이 겹칠 일이 없으며 visited의 값이 같은 값이 있는지를 통해 같은 열에 퀸이 있는지를 확인할 수 있다. 마지막으로 대각선은 대각선에 놓여있는 퀸들의 위치를 계산을 통해 구해낼 수 있다. abs(visited[x] - visited[i]) == x - i

그렇게 모든 퀸들의 위치가 정해지면(함수 queen의 x와 n값이 같아지면) 퀸을 놓는 하나의 방법을 찾은 것이므로 count의 값을 하나 늘려준다. count는 전역 변수로 사용하기 위해 global을 적어줬다.

 

조금만 잘 생각해보면 은근 쉬운 방법으로 풀 수 있다!

 

코드

import sys

count = 0

# 퀸을 놓으려면 놓으려는 자리에 가로, 세로, 대각선에 다른 퀸이 없는지 확인해야함
def check(x):
    for i in range(x):
        if visited[x] == visited[i] or abs(visited[x] - visited[i]) == x - i:
            return False
    return True


def queen(x, n):
    global count
    if x == n:
        count += 1
    else:
        for i in range(n):
            visited[x] = i
            if check(x):
                queen(x + 1, n)


n = int(sys.stdin.readline())
visited = [0] * n
queen(0, n)
print(count)