(파이썬) 백준 알고리즘 - 9663번

N-Queen

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

9663번: N-Queen

일단 체스에서 퀸은 수직, 수평, 대각선으로 이동할 수 있다.

문제에서는 N개의 퀸을 N*N칸에 배열해야 한다. 수직/수평에 있으면 공격할 수 있기 때문에 같은 행, 같은 열에는 퀸이 하나씩만 있을 수 있다. 그렇기 때문에 퀸의 위치를 N*N인 2차원 배열이 아닌, 1차원 배열로 표현할 수 있다.

N=4일때 가능한 이 배치에 대해서는 (2, 0, 4, 1)로 각각 (첫 번째 행, 두 번째 행, 세 번째 행, 네 번째 행)에서의 퀸의 위치를 나타낸다.

이와 같이 네 번째 행까지 가능한 위치에 퀸을 배열 가능한 경우의 수를 세면 된다.

def find(num):
    # 가능한 위치 탐색
    for i in range(num):
        # 마지막에 넣은 board[num]의 퀸이 이전의 퀸과
        # 같은 열에 위치하는지/대각선에 위치하는지 확인한다.
        if board[num] == board[i] or num - i == abs(board[num] - board[i]):
            return False
    return True
 
def nqueen(num):
    global count
    if num == N:
        count += 1
        # N번째 퀸 까지 배치한 경우, count를 증가시킴
    else:
        for i in range(N):
            # num번째 행 i열에 퀸을 위치시킨다
            board[num] = i
            # 퀸의 위치가 가능한 위치라면 다음 행에 퀸을 배치해본다.
            if find(num):
                nqueen(num +1)
 
N = int(input())
count = 0
board = [0] * N
nqueen(0)
print(count)

파이썬의 경우, 시간초과가 떠서 같은 내용의 코드를 C언어로 제출했다.

 

참고한 페이지

https://chanhuiseok.github.io/posts/baek-1/

[백준] 9663번 - N-Queen

https://cryptosalamander.tistory.com/58

[백준 / BOJ] - 9663번 N-Queen C++ 풀이