[Baekjoon 9663 / python / 골드4] N-Queen

n = int(input())

pos = [0] * n  # 퀸 위치 담을 리스트

flag_heng = [False] * n  # 행 배제

flag_a = [False] * ((n-1) * 2 + 1)  # 우상향 대각 배제

flag_b = [False] * ((n-1) * 2 + 1)  # 좌상향 대각 배제

count = 0  # 경우의 수

def set(i):

    global count

    for j in range(n):

        if not flag_heng[j] and not flag_a[i + j] and not flag_b[(n-1) + i - j]: # 행 , 대각, 대각 안전할 때

            pos[i] = j  # i번째 열의 j번째 행에 퀸을 둔다

            if i == n - 1:  # 마지막 열까지 n개의 퀸을 뒀을 때, 즉 경우의 수 하나를 찾았을 때

                count += 1

            else:  # 마지막 열이 아닐 때

                flag_heng[j] = flag_a[i + j] = flag_b[(n-1) + i - j] = True  # 퀸 공격범위를 배제한다

                set(i + 1)  #  다음 열에 퀸 두러 가기( 7열까지 다 둔 후 돌아오게 된다 )

                # 7열까지 갔다 왔으므로, 다시 1열부터 경우의 수를 찾기 위해 공격범위 배제했던걸 돌려놓는다

                flag_heng[j] = flag_a[i + j] = flag_b[(n-1) + i - j] = False

                # 이후 for문이 반복된다

set(0)

print(count)

 

크기가 N * N인 체스판에, N개의 퀸을, 서로 공격할 수 없게 배치하는 경우의 수를 모두 구하는 문제이다.

아주 어려웠지만 하노이 탑만큼 답이 없는 느낌은 아니었다.

 

1. 퀸의 위치를 담을 리스트

2. 퀸의 공격범위인 "행"을 배제할 리스트

3. 퀸의 공격범위인 "우상향 대각선"을 배제할 리스트

4. 퀸의 공격범위인 "좌상향 대각선"을 배제할 리스트

이 4개의 리스트를 미리 만들어 두어야 한다.

 

퀸의 공격범위인 "열"은 for j in range(n) 반복문에서 열 단위로 넘어가기 때문에 따로 리스트를 작성할 필요가 없다.

대각선은 종류가 2개(우상향,좌상향)이기 때문에, 각각 다른 배제 리스트를 작성한다.

 

0열~N열에서 퀸을 둘 때마다, 배제 리스트 3개(행, 대각, 대각)에 False값을 전부 추가해 주어야 한다.

 

N열까지 모두 진행했다면 반복문 진행을 위해 다시 1열로 돌아오게 되며, 배제해 두었던 리스트를 다시 False(퀸을 둘 수 있도록)로 돌려놓아야 한다.

이후 다시 새로운 경우의 수를 탐색하며, 이 과정이 N번 반복된다.

백트래킹 문제이다.