[Python] 백준 / gold / 9663번 (N-Queen)

문제 링크 : https://www.acmicpc.net/problem/9663

몰랐는데 백 트래킹에서 꽤 유명한 문제였다.

• N * N 모양의 체스 판에, N 개의 퀸을 서로 공격할 수 없는 위치에 배치하는 방법의 개수를 찾는 문제다.

이 문제 덕분에 간만에 코드에 대해 진짜 깊게 고민해본 것 같다.
처음에 답을 제출하고 맞왜틀을 계속 외쳤다.. 틀린 이유는 퀸의 배치는 combination으로 생각해야 하는데, permutation으로 답을 구했기 때문였다.

답은 맞았지만 시간 초과 코드 1

import sys
N = int(sys.stdin.readline())
answer = 0
direction = [(1, 0), (0, 1), (1, 1), (1, -1)]

queens = []

def dfs(trace, ban):
    print(trace)
    global answer
    if len(trace) == N:
        s = ''
        for x, y in sorted(trace):
            s += str(x) + str(y)
        if s not in queens:
            queens.append(s)
            print(queens)
            answer += 1
        return
    #print(trace)
    for x in range(N):
        for y in range(N):
            #print(x, y)
            if (x, y) not in ban:
                tempBan = set()
                trace.append((x, y))
                tempBan.add((x, y))

                for d in direction:
                    for i in range(-N, N+1):
                        nx = x + d[0]*i
                        ny = y + d[1]*i
                        if 0 <= nx < N and 0 <= ny < N:
                            tempBan.add((nx, ny))

                dfs(trace, ban | tempBan)
                trace.pop()



dfs([], set())
print('answer', answer)

그래서 queens 라는 리스트를 선언했고, trace를 문자열 형태로 타입 변경해서 집어넣어 중복을 제거했다. (permutation -> combination). 결론부터 말하면, 이건 답은 내지만 시간 효율이 진짜 안좋은 코드다.

왜 시간초과가 나지 고민하다가 결국 알아내지 못하고 잤다. 근데 자면서 생각하다가 문득 "어 이거 아니야?" 생각이 들어 일어나서 다시 풀어봤다. 현재 시각 04:45 am..

백트래킹 개념을 이해할 때는 State Space Tree (상태 공간 트리) 를 그려보는게 기본이라고 어디선가 들은 것 같다. SST를 그려보니 진짜로 이유를 찾게 됐다.

위의 시간초과 코드1의 상태 공간 트리다. 이 트리는 문제의 핵심을 반영하지 않았다.

핵심 : Queen은 같은 행의 어디든지 이동 할 수 있는데 이를 다르게 말하면, 한 행에는 반드시 하나의 Queen만이 존재해야 한다는 뜻이다.

그렇기 때문에 start 밑의 자식 노드 들이 (0,0) ~ (7,7) 로 뻗어나갈 필요가 없다. depth 1에서는 (0,0) ~ (0,7) depth2 에서는 (1,0) ~ (1,7) ... 이런식으로 트리를 뻗어나간다면 상태 공간 트리의 공간이 훨씬 작아지게 된다.

개선된 state space tree.

상태 공간 트리가 작아진 코드 2

import sys
N = int(sys.stdin.readline())
answer = 0
direction = [(1, 0), (0, 1), (1, 1), (1, -1)]


def dfs(row, trace, ban):
    global answer
    if len(trace) == N:
        answer += 1
        return

    for y in range(N):
        if (row, y) not in ban:
            tempBan = set()
            trace.append((row, y))
            tempBan.add((row, y))

            for d in direction:
                for i in range(-N, N + 1):
                    nx = row + d[0] * i
                    ny = y + d[1] * i
                    if 0 <= nx < N and 0 <= ny < N:
                        tempBan.add((nx, ny))

            dfs(row + 1, trace, ban | tempBan)
            trace.pop()


dfs(0, [], set())
print(answer)

dfs 매개 변수에 row를 추가해주고, row를 한 칸씩 내려가며 dfs 탐색을 진행했다. 개인적으로 horizontal, vertical, diagonal의 방향을 리스트에 담고 순회하는 저 로직이 직관적이라서 내 맘에 들었는데, len(direction) * (2N) 의 연산이 쓸데없이 많이 필요해서 시간초과가 났다.

정답 코드 😊

import sys
N = int(sys.stdin.readline())
answer = 0

def dfs(x, trace):  # x는 현재 행
    global answer
    if len(trace) == N:
        answer += 1
        return

    for y in range(N):
        check = True
        for row, col in trace:
            # 같은 열 제외
            if y == col:
                check = False
                break
            # 대각선 제외
            if abs(x-row) == abs(y-col):
                check = False
                break

        if check:
            trace.append((x, y))
            dfs(x+1, trace)
            trace.pop()


dfs(0, [])
print(answer)

최적화의 최적화. 효율성 테스트도 통과하게 됐다. 시간복잡도와 공간복잡도가 개선됐다. 2차원 리스트에서 Queen이 움직인다는 성질 때문에, 대각은 두 좌표의 차로 구할 수 있었다. 절댓값 함수 abs를 활용했다.