[백준/9663] N-Queen (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

n = int(input())
graph = [0] * n
count = 0

def is_promising(x):
    for i in range(x):
        if graph[x] == graph[i] or abs(graph[x] - graph[i]) == x - i:
            return False
    return True

def queen(x):
    global count
    if x == n:
        count += 1
        return
    else:
        for i in range(n):
            graph[x] = i
            if is_promising(x):
                queen(x+1)
queen(0)
print(count)

---

✔ 설명

#Tip

1. 굳이 2차원 배열을 쓸 필요가 없다. (1차원 배열의 인덱스 값을 사용)

2. graph[i] = j 는 'queen을 [i, j]에 놓는다'고 해석할 수 있다.

3. 퀸을 놓지 못하는 경우의 수를 따진다.

3-1. 같은 열에 다른 퀸이 있는 경우

3-2. 양 대각선에 다른 퀸이 있는 경우

---

✔ 후기

N-queen이 백트래킹 대표 문제라고 한다.

두 번 풀어봤었는데도 날려 풀었는지 매번 새롭다 (ᗒᗣᗕ)՞

다시 복습하면서 진짜 N-queen 문제 정복할테다

 

 

참고 자료:

https://chanhuiseok.github.io/posts/baek-1/

[백준] 9663번 - N-Queen

https://seongonion.tistory.com/103

[백준] 9663번 N-Queen - 파이썬(Python)