[Python] 백준 9663번: N-Queen

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

9663번: N-Queen

import sys
input = sys.stdin.readline


def setUnattackableCountRecursively(index):
    if index == N-1:
        for i in range(N):
            if isAvailable[i][index] == 0:
                global unattackableCount
                unattackableCount += 1
    else:
        for i in range(N):
            if isAvailable[i][index] == 0:
                setIsAvailable(1, i, index)
                setUnattackableCountRecursively(index+1)
                setIsAvailable(-1, i, index)


def setIsAvailable(num, x, y):
    # →
    curX, curY = x, y+1
    while curY <= N-1:
        isAvailable[curX][curY] += num

        curY += 1

    # ↗
    curX, curY = x-1, y+1
    while curX >= 0 and curY <= N-1:
        isAvailable[curX][curY] += num

        curX -= 1
        curY += 1

    # ↘
    curX, curY = x+1, y+1
    while curX <= N-1 and curY <= N-1:
        isAvailable[curX][curY] += num

        curX += 1
        curY += 1


if __name__ == '__main__':
    N = int(input())

    isAvailable = [[0]*N for _ in range(N)]

    unattackableCount = 0
    setUnattackableCountRecursively(0)
    print(unattackableCount)

우선 내 풀이는 기본적으로 재귀 + 백트래킹이 기초해있다.

 

isAvailable이라는 2차원 배열이 가장 핵심인데, 기본적으로 아래와 같이 초기화되어있다.

N=5

해당 배열이 0일 때, 해당 좌표를 탐색해도 된다는 의미이다.

 

재귀의 진행 방식은 아래와 같다.

for문을 돌면서 isAvailable 값이 0일 때만 다음 재귀 함수를 호출해주는 식이다.

 

다음으로, isAvailable은 위에서 언급했듯이 해당 좌표의 탐색 가능 여부를 나타낸다. 만약 초기 상태에서 (2, 0)에 대해 재귀를 호출한다면 아래와 같이 변할 것이다.

즉, 해당 좌표들에 놓으면 퀸으로부터 공격받을 수 있으므로, 위와 같이 값을 증가시켜주는 것이다.

 

그렇다면, isAvailable의 값을 True/False가 아니라 0, 1, 2, ...와 같이 정수로 둔 이유는 무엇인가?

그 이유는 바로 백트래킹 때문이다. 바로 위 표에서, (0, 1)을 탐색한다고 하자. 만약 숫자를 증가시키는 것이 아니라, True(0), False(1)로 두었다고 하면, 그 결과는 아래와 같을 것이다. 

위 상태에서 끝까지 탐색하고 돌아와서 백트래킹을 하게 되면 결과는 아래와 같아진다.

파란색으로 표시된 곳이, 원래의 값과 다르다.

이렇게 되면 백트래킹을 잘못 구현하게 된 것이다. 따라서 값을 1씩 증가, 감소시키고, 0일 때가 퀸을 둘 수 있는 상태로 지정해둔 것이다.

 

아무튼, 이런 식으로 isAvailable을 백트래킹으로 변경시키면서, 마지막 인덱스 때 조건을 검사하여 unattackableCount를 증가시켜준다. 재귀함수가 끝나게 되면, 마지막으로 unattackableCount를 출력해주면 된다.