[Algorithm] 백준 9663 N-Queen, 백트래킹 대표 문제 풀어보기🧐

지난 시간 백트래킹 기법에 대해 공부해봤다!
그래서 이번 시간에는, 백트래킹 대표 문제인 N-Queen 을 파이썬으로 풀어보려고 한다.

시이~작~😎

📌 백준 문제풀이 N-Queen

🤔 접근 방법

• 한 열에 퀸은 하나씩 놓을 수 있고, 각 행마다 무조건 1개의 퀸이 존재해야 한다.
• 체스의 퀸이 공격할 수 있는 범위는 상하좌우 및 대각선 방향이다.
• 이 점을 고려하여, 행과 열 중 하나를 기준으로 잡고 백트래킹 기법을 사용한다.
• 여기서는 행을 기준으로 잡았고, 각 행마다 다른 퀸이 공격할 수 있는지 체크하고, 퀸이 공격할 수 없다면 dfs(n+1)을 호출하여 그 다음 행에 대해 같은 작업을 반복한다.

💡 코드

from sys import stdin

def check(n):
    for i in range(n):
    	# 열 혹은 대각선이 같다면 0 리턴
        if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
            return 0
    return 1
        
def find(n):
    global res
    if n == N:
        res += 1
    else:
    	# 각 행에 퀸 놓기
        for i in range(N):
            row[n] = i
            # 행과 열, 대각선을 체크
            # 리턴값이 1이면 백트래킹 과정X
            if check(n):
                find(1)

N = int(stdin.readline())
row = [0] * N
res = 0
find(0)
print(res)

📌

• row[n] == row[i] ➡️ 열 확인
• abs(row[n]-row[i]) == n-i ➡️ 대각선 확인