[백준] #9663 N-Queen - 파이썬

문제

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

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

입력

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

출력

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

예제 입력 1 

8

예제 출력 1 

92

---

복기

1. 이중 루프를 돌면서 모든 경우를 탐색하는 경우로 생각했었는데, 각 행에는 하나의 퀸만 배치할 수 있기 때문에 행별로 확인하는 방식으로 풀어야 한다. 나는 처음에 퀸을 2개인거를 생각하고 풀었는데 문제를 제대로 읽어야겠다ㅠㅠ 즉, 한 행씩 순서대로 퀸을 배치하고, 그 행에서 가능한 모든 열을 시도한다.

. Q . .  (0행 1열)
. . . Q  (1행 3열)
Q . . .  (2행 0열)
. . Q .  (3행 2열)

2. 

---

솔루션

N = int(input())

def is_safe(row, col, placed):
    # 이전 행들의 퀸들과 충돌 확인
    for prev_row in range(row):
        prev_col = placed[prev_row]
        # 같은 열에 있는지 확인
        if prev_col == col:
            return False
        # 대각선에 있는지 확인
        if abs(prev_row-row) == abs(prev_col-col):
            return False
        return True


def back_traking(row, N, placed):
    global cnt
    if row == N: # 모든 퀸을 배치했다면
        cnt += 1
        return
    for col in range(N):
        if is_safe(row, col, placed):
            placed[row] = col # 퀸 배치
            back_traking(row+1, N, placed) # 다음 행으로
            placed[row] = -1 # 복구


cnt = 0
placed = [-1] * N # 각 행의 퀸이 위치한 열을 저장
back_traking(0, N, placed)
print(cnt)