Python - [백준]9663-N-Queen

출처

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

문제

N*N 체스판에 N개를 놓을때 대각선이나 상하좌우 겹치지 않도록 배치할 수 있는 경우의 수를 구하는 문제이다.

접근 방법

대표적인 백트래킹 문제이다. 재귀함수 호출을 이용해 모든 경우에 대해 탐색을 이어나가고, 호출한 재귀함수가 유망하지 않다면 다른 경우에대해 재귀함수를 호출하는 방식이다.

풀이

2차원 배열의 형식을 가진 판에 대해 탐색을 진행하는데, 1차원 배열만 이용하여 방문했는지 알아보는 visited를 인덱스 값을 이용하여 나타낼 수 있다.
i, j에 체스판을 놓기 위해서는 arr[i]에 j라는 값을 나타내면 i, j 값을 각각 기록할 수 있다. 퀸을 놓지 않은 부분에 대해서는 기록할 필요가 없기 때문에 이 방식을 사용한다.

유망한지 아닌지 검사하기 위하여 크게 두가지 경우로 나눌 수 있다.

1. 위 아래에 같은 퀸이 있는지

현재의 row까지의 값을 보고 중복되는 값이 있는지를 판별하는 경우이다.
arr[i]의 값과 내가 놓으려고 하는 arr[row]의 값을 반복문을 통해 비교해준다.

2. 대각선 방향에 퀸이 존재하는지

이것은 하나의 공식이 있는데, (현재 row - 임의의 row)의 절댓값과 (현재의 col - 임의의 col)의 절댓값이 같으면 대각선에 위치한다는 점을 이용한다.
예를들어, (2, 3)과 (4, 1)은 대각선 상에 위치하며 각각 (2 - 4)와 (3 - 1)은 절댓값 2로 일치한다.

위 두가지 방식을 사용하여 유망한지 여부를 검사하는 함수를 적용하여, 유망하다면 다음 재귀호출을 부르고 그렇지 않다면 호출하지 않도록 구성한다.

• 시간초과가 뜨는데 pypy3로 제출하면 통과가 가능하다.

n = int(input())
arr = [0]*n
solution = 0

def is_possible(r):
    for i in range(0, r):
        if arr[i] == arr[r] or abs(r - i) == abs(arr[r] - arr[i]):
            return 0
    return 1

def recursive(r):
    global solution
    if r == n:
        solution += 1
        return
        
    else:
        for i in range(n):
            arr[r] = i
            if is_possible(r):
                recursive(r+1)
    
    
recursive(0)
print(solution)