[알고리즘] 백트랙킹 (Backtracking)

백트랙킹(Backtracking) 이란?

---

백트래킹은 한정 조건에 대해 해를 찾는 탐색 및 최적화 문제의 해결 전략이다. 백트래킹은 모든 경우에 대해 탐색을 수행하는 과정에서 불필요한 경로는 배제하여 효율성을 높이는 방식으로 동작한다. 한정조건에 대해서 경우의 수를 시도하기 때문에 단순 다중 for문을 사용하는 것보다 효율적으로 동작한다. 

 

Backtracking의 문제 해결 전략

---

1. 문제를 풀기 위한 모든 가능한 해의 조합을 정의함
2. 각 단계에서 현재 상태가 문제의 한정 조건을 만족하는 지 검사하고, 해가 될 수 없는 경로라면 가지치기를 통해 정답 경로에서 배제함
3. 정답이 될 수 있는 경로를 따라 재귀적으로 진행을 한다. 특정 경로가 조건을 만족하지 못하면 이전 단계로 돌아가 경로를 탐색함
4.  탐색하다가 문제를 해결하면 종료하고, 그렇지 않으면 다른 경로를 탐색하기 위해 이전 경로로 되돌아감

DFS와 Backtracking

---

DFS와 Backtracking 모두 탐색을 위한 알고리즘으로 비슷해 보이지만 다른점이 있다. 

• DFS
  • 모든 경로를 탐색함
    • DFS는 모든 노드를 방문해가며 경로를 찾는 것이 목표이다. 
• Backtracking
  • 조건을 만족하는 경로만 탐색
    • Backtracking은 경로를 탐색하다 조건을 만족하지 않는다면 탐색을 중단하고 이전 단계로 돌아가 다른 경로를 탐색한다. 

Backtracking 구현 방식

---

def backtracking(n):
	if 정답:
    	정답_출력_or_저장()
        return
    for node in child_nodes:
    	if 조건_만족(node):
        	자식노드로_이동
            backtracking(n+1)
            부모노드로_이동

Backtracking 예시

---

Backtracking의 가장 유명한 문제는 N-Queen 문제이다. 

문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째줄에 N이 주어짐 ( 1 <= N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력

예제

N = 8
answer = 92

import sys

# 체스판의 크기를 입력받음
n = int(input())

# 현재 배치한 퀸이 이전에 배치한 퀸들과 충돌하는지 확인
def attack(x):
	for i in range(x):
    	# 같은 열에 있거나, 대각선 상에 있으면 충돌임
    	if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
        	return True
        return False

# start는 현재 놓고 있는 행
def dfs(start):
	global cnt
    모든 행에 퀸을 배치했다면 유효한 배치이므로 cnt 증가
    if start == n:
    	cnt += 1
    else:
    	for i in range(n):
        	row[start] = i
            # 충돌이 없다면 다음 행을 진행
            if not attack(start):
            	dfs(start + 1)

# 각 행에 퀸을 저장할 리스트 초기화
row = [0] * n
# 가능한 가짓수를 세는 변수 초기화
cnt = 0
dfs(0)

print(cnt)