[ 2023-02-27 🙀 TIL ]

백준 9663번

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

def back(x):
    for i in range(x):
        if queen_li[x] == queen_li[i] or abs(queen_li[x] - queen_li[i]) == abs(x - i):
            # 퀸의 이동 규칙 -> 가로, 세로, 대각선 에 맞는 위치에 다음 퀸을 넣을 수 없는 조건으로 판단
            return False

    return True


'''
n = 3 👇
	 [0,0][0,1][0,2]
	 [1,0][1,1][1,2]
	 [2,0][2,1][2,2]
'''

def queen(x=0):
    global count
    if x == n:
        count += 1
        return

    for y in range(n):
        queen_li[x] = y # [x, y]에 queen 위치 [0,0]->[0,1]->[0,2]

        if back(x): # 
            queen(x+1) # 다음 열에 queen 넗을 수 있는 지 확인


queen()
print(count)

백트래킹을 이용하여 해결하는 문제였지만 결국 검색하여 해결하였습니다.

백트래킹에 관한 알고리즘을 더욱 풀어보면서 학습을 해야 할 것 같습니다.