[백트래킹] N-Queen문제

백트래킹이란?

해를 찾기 위해 DFS방식으로 탐색하다가 해당 루트가 유망한지(Promising) 검사하여 조건이 맞지 않다면 가지치기(Pruning)하고 다른 루트로 돌아가 최적의 해를 찾는 방법이다.

상태 공간 트리(State Space Tree)

문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이다.

---

N-Queen문제

대표적인 백트레킹 문제이다.

백준 9663번 문제: https://www.acmicpc.net/problem/9663

n = int(input())

row = [250] * n
answer = 0

#현재 레벨에서 놓을 수 있는지 없는지 체크하는 함수 (행[자동 생략], 열, 대각선)
def can(level):
    for i in range(level):
        if row[level] == row[i] or abs(row[level] - row[i]) == level - i:   #열위치가 같은 조건 | 열위치 차이와, 행위치 차이가 같다면 대각선
            return False
    return True


def dfs(level):
    global answer

    if level == n:
        answer += 1
        return
    else:
        for i in range(n):  #퀸을 배치할 열 
            row[level] = i  #퀸을 level행 i열에 배치
            if can(level):
                dfs(level + 1)

dfs(0)
print(answer)

9663번: N-Queen

 

 

 

참고자료: https://www.fun-coding.org/Chapter21-backtracking-live.html

파이썬과 컴퓨터 사이언스(고급 알고리즘): 백 트래킹 기법의 이해 - 잔재미코딩

이해자료: https://chanhuiseok.github.io/posts/baek-1/

[백준] 9663번 - N-Queen