백준 알고리즘 - 9663 - N Queen

문제

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

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

---

입력

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

---

출력

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

---

예제 입력 1 복사

8

예제 출력 1 복사

92

---

코드

N = int(input())
check = [0] * N
answer = 0

def queen(x): # 현재 위치에서 윗줄에 공격할 수 있는 퀸이 존재하는지 확인
    for i in range(x):
        if check[x] == check[i] or abs(check[x] - check[i]) == x - i:
            return 0
    return 1

def dfs(x):
    global answer
    
    if x == N: # 마지막 행까지 퀸을 놓아본다.
        answer += 1
    else:
        for i in range(N):
            check[x] = i # 퀸을 놓아본다.
            if queen(x): # 퀸을 놓을 수 있다면?
                dfs(x + 1) 

dfs(0)
print(answer)

 

1~3 줄 : 퀸 N개를 입력 받고, 퀸을 놓는 자리를 나타내는 배열을 check로, 전체 경우의 수를 answer로 설정합니다.

 

5~9 줄 : 같은 열에 있어서도 안되고 대각선에 있어서도 안된다. 이를 확인하는 queen() 함수를 만듭니다. 같은 열과 대각선에 퀸이 있다면 0(False)을 리턴하고 그렇지 않다면 1(True)을 리턴합니다.

 

11~20 줄 : 각각의 열에 퀸을 놓을 수 있을지 판단합니다. 만약 퀸을 어디에도 놓을 수 없다면 재귀를 탈출하여 이전 열로 돌아가서 퀸을 놓았던 자리를 다시 0(False)으로 돌려놓습니다. 그리고 그 열의 다음 행에 퀸을 놓을 수 있는지 검사하는 것을 반복해 나갑니다.