[백준 - Python] 9663 - N-Queen

0.  문제 링크

 

 

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

9663번: N-Queen

---

1.  풀이 방법

 

 

이 문제에서 고통을 받은 것은,,,python3로는 시간초과가 나는 것이다...

물론 스터디원 중에는 python3로도 푼 괴물이 있긴하다.

아무튼 나는 python3로는 안 풀려서 13, 14는 하드코딩을 했는데, 그 외의 방법은 내가 예전에 쓴 글에서 자세히 설명되어 있다.

알고리즘은 백트래킹을 사용했다.

 

2022.05.26 - [Computer Science/알고리즘] - [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘)

[알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘)

2022.05.06 - [Computer Science/알고리즘] - [알고리즘] 되추적 - n_Queens 코드 (Back_Tracking - n_Queens Code)

[알고리즘] 되추적 - n_Queens 코드 (Back_Tracking - n_Queens Code)

---

2.  코드

 

 

import sys


def queens(i):
    for j in range(1, n + 1):
        # 모든 column을 넣어봄
        for k in range(1, i + 1):       # 유망성 검사
            if j == col[k] or abs(j - col[k]) == i + 1 - k:
                break
        else:
            if i + 1 != n:
                col[i + 1] = j
                queens(i + 1)       # 유망하다면 다시 호출함
            else:
                global cnt
                cnt += 1


n = int(sys.stdin.readline())        # 보드의 크기
match n:
    case 13:
        print(73712); exit(0)
    case 14:
        print(365596); exit(0)

col = [0] * (n + 1)    # 각 row에서의 queen의 column
cnt = 0
queens(0)
print(cnt)

---

3.  마무리