[BOJ] 9663번 N-Queen / 사용언어 : 파이썬(python)

※ 문제링크

9663번: N-Queen

해당문제는 백트래킹 알고리즘의 대표적인 문제로 DFS, 브루스포트 알고리즘을 추가로 활용하여 해결할 수 있는 문제였다. 처음에는 2차원 배열을 활용하여 문제를 해결하려고 하였으나, N의 값에 따라 탐색할 경우의 수가 급격하게 증가하기 때문에 문제 해결방안으로 부적절한 것을 알게되었다. 다른 방법의  풀이를 생각하던 중 퀸의 동작원리 상 한개의 행에는 1개의 퀸밖에 들어갈 수 없고, N x N 체스판에 N개의 퀸을 놓기위해서는 각 행에 퀸이 하나씩 반드시 들어가야한다는 것을 고려하여 1차원 배열로 모든 경우의 수를 탐색하는 방법으로 문제를 해결하였다. 다만, 해당 코드도 Python으로는 통과가 불가능하였으나, 구현방법에 대한 이해와 알고리즘에 대한 이래는 충분히 할 수 있었다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 바탕으로 길이가 N인 모든 구성요소가 0으로 이루어진 리스트를 작성해준다. (+ 1차원 리스트의 인덱스값을 행[y좌표]으로, 해당 인덱스가 가지는 value를 열[x좌표]로 가정하고 구현)

2. 퀸의 동작원리를 고려하여 퀸이 서로를 공격할 수 있는지 여부를 판단할 check함수를 구현한다.

3. 재귀를 이용하여 특정위치에 놓을 수 있는 퀸들의 위치와 경우의 수를 판단할 check_Q함수를 check함수를 이용하여 구현해준다.

4. 작성한 함수를 동작시킨 후 ans값을 출력한다.

 

# 작동원리 : 1차원 배열의 인덱스를 x좌표로, 배열의 값을 y좌표로 구성
# 퀸의 동작원리상 1개의 행에 1개의 퀸 밖에 놓을 수 없음.
# 1개의 행에 1개의 퀸밖에 들어가지 못하기 때문에 1차원 배열로 구현 가능
# PyPy3로만 통과가능
N = int(input())

ans = 0
row = [0] * N

def check(y):
    for x in range(y):
        if row[y] == row[x] or abs(row[y] - row[x]) == abs(y - x): # 같은 열이면 False, 대각선위치에 있으면 False
            return False    
    return True

def check_Q(y):
    global ans
    if y == N:
        ans += 1

    else:
        for x in range(N):
            # [y, x]에 퀸을 놓겠다.(y좌표, x좌표)
            row[y] = x
            if check(y):
                check_Q(y+1)
                

check_Q(0)
print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.