백준 9663번 N-Queen

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #브루트포스 알고리즘 #백트래킹

---

조건

시간 제한	메모리 제한
10 초	128 MB

---

문제

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

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

8

출력

92

---

코드(파이썬)

def back_track(row):
    global cnt
    
    if row == n:
        cnt += 1
        return

    visited = set(queen)
    for i in range(row):
        if queen[i] - row + i >= 0:
            visited.add(queen[i] - row + i)
            
        if queen[i] + row - i <= n-1:
            visited.add(queen[i] + row - i)
    
    for next_ in range(n):
        if next_ not in visited:
            queen[row] = next_
            back_track(row+1)
            queen[row] = -1

n = int(input())
queen = [-1 for _ in range(n)]
cnt = 0

for start in range(n):
    queen[0] = start
    back_track(1)
    queen[0] = -1

print(cnt)

---

특이사항

• 퀸의 상태를 queen 리스트에 저장(queen[1] = 3 <-> (2,4) 위치에 퀸)
• queen 리스트를 이용해 현재 행에서 갈 수 없는 열을 visited 리스트에 저장
• 이후에는 DFS 반복

---

참고문헌

-