[백준알고리즘/9663번/파이썬] N-Queen

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

9663번: N-Queen

 

문제: N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제.

 

 

풀이 방법: 백 트래킹

 

 

풀이 코드:

n = int(input())
board = [0] * n
visited = [0]*n
count = 0


def checkAvailable(col):
    for i in range(col):
        if abs(board[col] - board[i]) == col - i:
            return False
    return True

def searchGraph(col):
    global count
    if col == n:
        count += 1
        return

    for i in range(n):
        if col == 0 and n % 2 == 0 and i == n/2:  # 보드가 짝수 size 일 경우, 대칭이기 때문에 *2 연산으로 연산 횟수 줄임
            return
        if visited[i]:
            continue
        board[col] = i
        if checkAvailable(col):
            visited[i] = True
            searchGraph(col+1)
            visited[i] = False

searchGraph(0)

if n % 2 == 0:
    print(count*2)
else:
    print(count)

 

풀이 설명:

board = [0] * n
visited = [0] * n

board에는 각 행에 퀸이 몇번째 열에 있는지 여부를 저장하는 배열이고, visited는 각 열에 퀸이 존재하는지 여부를 저장하는 배열입니다.

 

def checkAvailable(col):
    for i in range(col):
        if abs(board[col] - board[i]) == col - i:
            return False
    return True

checkAvailable은 퀸이 놓여질 수 있는지 여부를 판단하는 함수 입니다.

 

예를들어,  (0 , 0)과 (1 , 1)은 서로 대각선에 위치하는 점 입니다.  (4 , 5)와 (6 , 8)도 서로 대각선의 위치에 존재하는 점 입니다.

대각선에 위치하는 점들 끼리는 행의 값 차이와 열의 값 차이가 서로 같습니다.

따라서, 다음 조건을 통해 대각선 상에 위치한다면 False를 return 하도록 구성하였습니다.

 

def searchGraph(col):
    global count
    if col == n:
        count += 1
        return

    for i in range(n):
        if col == 0 and n % 2 == 0 and i == n/2:  # 보드가 짝수 size 일 경우, 대칭이기 때문에 *2 연산으로 연산 횟수 줄임
            return
        if visited[i]:
            continue
        board[col] = i
        if checkAvailable(col):
            visited[i] = True
            searchGraph(col+1)
            visited[i] = False

searchGraph 함수는 최종적으로 체스 보드에 퀸이 들어갈 수 있는 경우의 수를 탐색하는 함수 입니다.

 

한 행에 1개의 퀸만 넣는다고 하였을 때, 퀸이 체스 보드에 들어갈 수 있는 위치는 다음 조건을 만족하여야 합니다.

1. 앞선 행의 대각선 위치에 퀸이 존재하지 않을 것

2. 같은 열에 퀸이 존재하지 않을 것

 

visited 배열을 통애 같은 열 안에 퀸이 존재하는지 확인하고, 같은 열에 퀸이 존재하지 않을 경우에 대각선에 퀸이 존재하는지 확인합니다.

즉, 두 조건을 만족하면 visited에 해당 열에 퀸이 존재한다고 표시하고(True) 재귀를 통해 다음 행에 대한 searchGraph 함수를 호출합니다.

 

함수에 들어오는 행의 값이 n일 경우, 0~ n-1번째 행에 퀸이 채워졌다는 의미이므로 1개를 카운트 해줍니다.

 

추가적으로 시간을 줄이기 위해, 짝수 size의 체스판에서는 경우의 수가 좌우 대칭을 이루기 때문에 절반까지만 세고 x2를 해주는 방식을 사용하였습니다.