[백준] 9663번 N-Queen

문제 출처 : https://www.acmicpc.net/problem/9663

정답 코드 💻

n = int(input())

ans = 0
row = [0] * n

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

def n_queens(x):
    global ans

    if x == n:
        ans += 1
        return

    else:
        for i in range(n):      # [x, i]에 퀸 놓기
            row[x] = i
            if is_promising(x):
                n_queens(x + 1)

n_queens(0)
print(ans)

👉🏻 재귀함수로 백트래킹 기법을 사용하여 모든 조합을 구하면 된다.

설명

👉🏻 1번째 줄부터 확인해서 한 줄씩 내려가며 확인한다.

👉🏻 2번째 줄부터 확인해서 끝까지 보고 마무리하면 다시 1번째 줄 2번째 칸을 확인한다.

👉🏻 1번째 줄 2번째 칸을 확인하여 횟수를 올린다.

👉🏻 row는 몇 번째 줄의 몇 번째 칸에 있는 지 확인하는 것이다.

👉🏻 row = [1,3,0,2]

첫번째 줄 1번 인덱스에 퀸이 있다.
두번째 줄 3번 인덱스에 퀸이 있다.
세번째 줄 0번 인덱스에 퀸이 있다.
네번째 줄 2번 인덱스에 퀸이 있다.

느낀 점 ✏️

세상에 넘 어렵다... :(