[백준] / [Python] / [9663] N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제

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

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

입력

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

출력

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

---

https://sso-feeling.tistory.com/415

[백준] 9663 N-Queen 파이썬 풀이 (백트래킹)

위 블로그에 그림으로 잘 설명해두어서 이해가 쉬웠다.

 

Python 3로 실행하면 시간초과.. PyPy3로 실행

def dfs(queen, n, row):
    count = 0
    
    if n == row:
        return 1
    
    # 가로로 한번만 진행
    for col in range(n):
        queen[row] = col
        
        # for-else구문
        for x in range(row):
            # 세로로 겹치면 안됨
            if queen[x] == queen[row]: 
                break
                
            # 대각선으로 겹치면 안됨
            if abs(queen[x]-queen[row]) == (row-x):
                break
        else:
            count += dfs(queen, n, row+1)
            
    return count

N = int(input())

queen = [0] * N       
print(dfs(queen, N, 0))