Backtracking이란

Backtracking

- 모든 조합을 시도해서 문제의 해를 찾음, 단 해의 조건을 위반하는 경우 끝까지 해를 구하지 않고 그만둠

- 완전 탐색 방법인 DFS, BFS와는 달리, 해의 가능성이 없는 경우를 탐색하지 않고 다음 탐색 진행

- 주로 DFS 탐색 도중 해의 가능성이 없는 노드를 가지치기하는 방식으로 진행

 

Promising

- 해당 노드가 조건에 맞는지를 검사

 

Pruning (가지치기)

- 조건에 맞지 않으면 탐색을 더 이상 진행하지 않고, 바로 다음 노드로 넘어가서 탐색 시간을 절약함

 

N-Queen

- 크기가 N * N인 체스 판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 문제

1. Promising

-> 한 행에는 하나의 퀸만 위치할 수 있음, 맨 위부터 차례로 퀸을 배치

-> 수직 방향, 대각선 방향으로 퀸의 공격이 가능한 지 확인

2. Pruning

-> 다음 행에 퀸을 배치한 공간이 없을 경우, 이전 행의 퀸 위치를 바꿈

n = int(input())
queen = [0] * n
result = 0

def isAdjecent(idx):
    for i in range(idx):
    	# 수직 방향, 대각선 방향 검사
        if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
            return False

    return True

def dfs(idx):
    if idx == n:
        global result
        result += 1
        return

    for i in range(n):
        queen[idx] = i
        if isAdjecent(idx):
            dfs(idx + 1)

dfs(0)
print(result)

 

 

 

출처

https://chanhuiseok.github.io/posts/algo-23/

https://thd0011.tistory.com/19

https://fomaios.tistory.com/entry/Algorithm-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking%EC%9D%B4%EB%9E%80

https://www.fun-coding.org/Chapter21-backtracking-live.html

https://hongcoding.tistory.com/m/117