[백준] 9663 N-Queen (Python 파이썬)

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

9663번: N-Queen

문제 설명

• N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
• N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

---

풀이 과정

체스판의 퀸은 자신의 줄, 칸, 대각선에 위치한 말을 잡을 수 있다.

이러한 퀸을 N x N의 체스판에 N개 놓을 때 서로 공격할 수 없도록 놓아야 한다.

 

이 문제는 퀸의 위치를 바꾸어가며 경우의 수를 구하는 DFS+백트래킹 문제이다.

 

일단 퀸은 한 줄에 1개밖에 놓지 못하므로

2차원배열이 아닌 1차원 배열을 만들어

각 배열의 칸에는 그 행의 퀸의 위치를 넣는다.

 

그리고 퀸이 같은 열에 존재하거나 같은 대각선에 존재하는지를 확인하여

존재하지 않는다면 퀸을 놓음으로써 경우의 수를 늘려간다.

n = int(input())
queen = [0] * n
result = 0

def isAdjecent(idx):
    for i in range(idx):
        if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
            return False

    return True

def dfs(idx):
    if idx == n:
        global result
        result += 1
        return

    for i in range(n):
        queen[idx] = i
        if isAdjecent(idx):
            dfs(idx + 1)

dfs(0)
print(result)

현재 이 코드는 시간초과가 난다. (조건이 더 추가된 것 같음)

파이썬으로는 시간초과를 해결하려면 더 많은 배열을 추가하여 다른 조건들을 넣어주어야 한다고 한다.

 

현재 문제는 15x15문제로 정답이 정해져있으니

시간초과가 해결되지 않는다면 다음 코드를 제출하는 것을 추천한다(야매)

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !