[백준] 9663번 - N-Queen

동현·2022년 10월 31일

백준 완전탐색 코딩테스트 파이썬

백준 온라인 저지 문제 풀이

목록 보기

5/8

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 예제 입력 / 출력

8

92

5. 풀이 과정

퀸은 다음과 같이 상하좌우 대각선을 공격하기에 퀸에게 공격을 받지 않는 법을 정리하면 다음과 같다.

같은 행에 위치하면 안 된다.

같은 열에 위치하면 안 된다.

대각선상에 위치하면 안 된다.

우선 각각의 퀸들은 같은 행에 위치할 수 없다. 이를 이용해 굳이 2차원 리스트를 사용하지 않고 위치를 표현할 수 있다. 퀸의 위치를 담은 리스트를 board라고 하겠다.

다음과 같이 퀸이 배치 되어있을 때를 예로 들자면 인덱스를 행, 값을 열로 처리하면 아래와 같이 퀸의 위치를 간단히 표현할 수 있다.

board = [0, 2, 4, 1, 3]

board 리스트에서 값은 즉 열을 의미하기 때문에, 같은 열에 위치하지 않기 위해서는 board에 같은 값이 있는지 확인하면 된다.

대각선에 위치하는 것도 하나의 규칙을 찾을 수 있는데 대각선에 위치한다면 비교하는 대상의 위치에서 열과 행의 차이가 똑같다.
따라서 두 퀸을 비교할 때 인덱스의 차이와 값의 차이를 비교해 똑같다면 대각선에 위치하는 것으로 판단할 수 있다.

def nqueen(current):
    # current는 현재 몇 개의 퀸이 배치되었는지 의미하는 변수
    global answer
    
    if current == n:
        answer += 1
        return
    
    for i in range(n):
        is_promising = True
        for j in range(current):
            # 이미 배치된 퀸들을 통해 놓을 수 있는지 여부 판별
            # 같은 열, 대각선상에 존재 불가
            # 행 번호 차이 = 열 번호 차이라면 같은 대각선상에 존재하는 것
            if board[j] == i or abs(current - j) == abs(i - board[j]):
                is_promising = False
                break
        if is_promising:
            board[current] = i
            nqueen(current + 1)

n = int(input())
board = [-1] * n
answer = 0

nqueen(0)

print(answer)