백준 / N-Queen / 9663번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: N-Queen / 9663번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/9663
 

문제 설명

시간 제한 10초

---

나의 풀이

def check(n, board, y, x):
    # 위쪽 열 확인
    for i in range(y):
        if board[i][x] == 1:
            return False

    # 왼쪽 위 대각선 확인
    i, j = y - 1, x - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1

    # 오른쪽 위 대각선 확인
    i, j = y - 1, x + 1
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1

    return True


def solve(n, board, y, result):
    if y == n:
        result[0] += 1
        return

    for x in range(n):
        if check(n, board, y, x):
            board[y][x] = 1
            solve(n, board, y + 1, result)
            board[y][x] = 0  # 백트래킹


def main():
    n = int(input())
    board = [[0] * n for _ in range(n)]
    result = [0]  # 정답 저장용

    solve(n, board, 0, result)
    print(result[0])


if __name__ == "__main__":
    main()

NxN 배열을 생성해서 0은 빈 상태 1은 퀸을 둔상태로 하나씩 두기 시작합니다! 퀸을 두었을 때 퀸이 다른 퀸으로부터 위협을 받는지 확인하고 두게 됩니다!

위 그림처럼 모든 경로를 파악하는 방법을 생각했습니다. 하지만 위 방법은 NxN 배열을 생성해서 파악하므로 시간 복잡도가 초과했습니다.

정답 코드

def solve(n, y, col, diag1, diag2, result):
    if y == n:
        result[0] += 1
        return

    for x in range(n):
        if not col[x] and not diag1[y + x] and not diag2[y - x + n - 1]:
            col[x] = diag1[y + x] = diag2[y - x + n - 1] = True
            solve(n, y + 1, col, diag1, diag2, result)
            col[x] = diag1[y + x] = diag2[y - x + n - 1] = False


def main():
    n = int(input())
    col = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)
    result = [0]
    solve(n, 0, col, diag1, diag2, result)
    print(result[0])


if __name__ == "__main__":
    main()

위 코드는 board를 사용하지않고 col[x]: 열 충돌 체크, diag1[y + x]: 오른쪽 위 대각선 충돌 체크, diag2[y - x + n - 1]: 왼쪽 위 대각선 충돌 체크만 했습니다 그럼 매 순간 O(1)의 시간으로 해결할 수 있습니다.

---

※ 알아야 할 것

재귀함수를 이용하여 시뮬레이션을 진행하는 문제입니다!