[백준] 9663번 : N-Queen - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

9663번: N-Queen

 

1. 문제 설명

2. 풀이과정

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 퀸을 배치하는 함수를 정의한다. def nQueen(n)
3. 퀸을 배치할 수 있는 모든 경우의 수를 저장할 변수를 외부에서 정의하고 함수 내부에서도 그대로 사용할 수 있도록 global 변수로 가져온다. global count
4. 만약 현재 놓을 퀸이 마지막 퀸이면 if (n == N)
5. 경우의 수를 증가시킨다. count += 1
6. 한 가지 경우를 찾았으므로 종료한다. return
7. 마지막 퀸이 아니었다면 해당 퀸을 놓을 위치를 전체 체스판의 크기만큼 반복하며 for i in range(N)
8. 해당 위치에 이미 퀸이 놓여있는지 확인하고 만약 퀸이 이미 놓여 있다면 (한 열에 하나씩 배치 가능) if (visit[i])
9. 해당 위치에는 현재 퀸을 놓을 수 없기 때문에 퀸을 놓지 않고 다음 위치로 넘어간다. continue
10. 반면에 해당 위치에 퀸을 놓을 수 있다면 해당 열에 퀸을 놓는다. col[n] = i
11. 퀸을 놓고 해당 퀸이 올바르게 놓였는지 확인한다. if (promising(n))
12. 만약 퀸을 올바르게 놓을 수 있다면 해당 열은 더 이상 퀸을 놓을 수 없다. visit[i] = True
13. 해당 퀸을 놓았으므로 다음 퀸을 배치한다. nQueen(n + 1)
14. 가능한 모든 경우를 다 찾고 돌아와 다른 위치에도 놓을 수 있는지 확인해 보기 위해 해당 열의 퀸을 제거한다. visit[i] = False
15. 퀸이 올바른 위치에 놓였는지 확인하는 함수를 정의한다. def promising(n)
16. 퀸을 놓을 수 있는 조건은 우선 한 열에 하나의 퀸을 배치해야 합니다. 또한 퀸은 상하좌우뿐만 아니라 대각선으로도 이동할 수 있기 때문에 한 대각선에 하나의 퀸만 배치해야 합니다.
17. 한 열에 하나의 퀸을 배치하는 조건은 각 퀸이 놓인 열의 번호를 확인하면 되고
18. 각 대각선에 하나의 퀸을 배치하는 조건은 배치된 두 퀸을 각 점으로 하는 직각삼각형을 만들어볼 때, 직각이등변삼각형이면 안된다. (직각이등변삼각형이면 두 퀸은 한 대각선 위에 배치되어 있음)
19. 하여 제일 위 행부터 현재 배치한 행 전까지 반복하며 for i in range(n)
20. 위 두 조건이 만족하는지 확인하고 하나라도 만족하지 않는다면 if (col[n] == col[i]) or (abs(col[n] - col[i]) == n - i)
21. 현재 배치한 퀸은 올바른 위치가 아니라고 반환합니다. return False
22. 반면에 두 조건을 모두 만족한다면 퀸은 올바른 위치에 배치되었다고 반환합니다. return True 
23. 체스판에 놓을 퀸의 개수를 입력받고 N = int(sys.stdin.readline())
24. 각 행별로 퀸이 어느 열에 배치되었는지 저장할 리스트를 생성한다. col = [0] * N
25. 각 열에 행이 배치되어 있는지 저장할 리스트도 생성한다. visit = [False] * N
26. 퀸을 배치할 수 있는 모든 경우의 수를 저장할 변수를 생성하고 초기화한다. count = 0
27. 퀸을 배치할 함수를 실행하고 nQueen(0)
28. 구해진 가능한 모든 경우의 수를 출력한다. print(count)

위 코드는 틀린 부분이 없다. 하지만 코드를 Python3로 제출하면 시간초과가 발생한다.

하여 PyPy3로 제출하였다. PyPy3로 제출하면 시간초과가 발생하지 않고 통과가 된다.

이는 문제에 따라 다르긴 하지만 일반적으로 PyPy3가 Python3보다 빠른 경향이 있기 때문에 이러한 경우가 발생했다.

 

또한 위 코드를 작성하여 입력 가능한 값인 1부터 15까지의 결과를 미리 확인하고 각 경우별 결과를 리스트에 저장하여 간단하게 출력하는 방법으로 코드를 작성하면 가장 빠른 시간으로 해결할 수 있다.

import sys

N = int(sys.stdin.readline())

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

반응형

3. 소스코드

import sys

def nQueen(n):
    global count
    
    if (n == N):
        count += 1
        return
    
    for i in range(N):
        if (visit[i]):
            continue

        col[n] = i
        if (promising(n)):
            visit[i] = True
            nQueen(n + 1)
            visit[i] = False

def promising(n):
    for i in range(n):
        if (col[n] == col[i]) or (abs(col[n] - col[i]) == n - i):
            return False
        
    return True


N = int(sys.stdin.readline())

col = [0] * N
visit = [False] * N

count = 0
nQueen(0)
print(count)