[백준/pypy3] 9663번 : N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

정답

N = int(input())
count = 0

# row : 행 / right : 우상향 대각선 / left : 좌상향 대각선
row, right, left = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)

def solve(j):
    global count
    # N개의 퀸을 다 놓았을 때
    if j == N:
        count += 1
        return

    for i in range(N):
        # 모든 방향이 False일 때 = 퀸을 놓을 수 있을 때
        if not (row[i] or right[j + i] or left[N - 1 + j - i]):
            row[i] = right[j+i] = left[N-1+j-i] = True
            solve(j+1)
            row[i] = right[j+i] = left[N-1+j-i] = False


solve(0)
print(count)

---

이 문제는 파이썬을 통해 풀 경우 시간 초과가 발생하기 때문에 pypy3를 사용해야 풀 수 있다.

# row : 행 / right : 우상향 대각선 / left : 좌상향 대각선
row, right, left = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)

좌표의 두 인덱스의 합 또는 차가 다른 좌표의 합 또는 차가 같다면 같은 대각선 상에 존재함을 이용한다.

예를 들어 (0,2), (1,1), (2,0)의 두 인덱스의 합은 2로 모두 같으므로 같은 우상향 대각선 상에 위치한다.

대각선을 나타내는 right와 left는 두 인덱스의 합과 차로 이루어지므로 2*N-1개의 인덱스가 필요하다.

 

def solve(j):
    global count
    # N개의 퀸을 다 놓았을 때
    if j == N:
        count += 1
        return

solve 함수를 만들고 행을 의미할 j를 인자로 사용하여 모든 행에 퀸을 놓을 것이다.

j가 N과 같다면 놓아야 하는 개수의 퀸을 각 행마다 다 놓았다는 뜻이기 때문에

퀸을 놓는 방법의 수를 의미하는 count에 1을 더해주고 return 한다.

 

for i in range(N):
        # 모든 방향이 False일 때 = 퀸을 놓을 수 있을 때
        if not (row[i] or right[j + i] or left[N - 1 + j - i]):
            row[i] = right[j+i] = left[N-1+j-i] = True
            solve(j+1)
            row[i] = right[j+i] = left[N-1+j-i] = False

이제 맨 위 행부터 시작하여 순서대로 내려가면서 모든 열에 퀸을 놓는다.

모든 열 i에 대하여 다음 반복문을 실행한다.

해당 열의 행, 대각선이 모두 False라면 퀸을 놓을 수 있다는 뜻이므로

해당 열의 행, 대각선을 True로 바꿔주고 다음 행인 solve(j+1)을 호출한다.

다음 경우의 수를 세기 위해 행과 대각선을 의미하는 row, right, left를 다시 Flase로 초기화한다.

 

아래 주소의 설명을 참고하였다.

rebas.kr/761