[Algorithm] 백트레킹

Об этом предложении

백트래킹(Backtracking) 1. 백트래킹이란? 백트래킹은 여러 가지 선택지가 존재하는 상황에서 하나를 선택하고, 그 선택을 기반으로 다음 선택을 이어가며 정답을 찾는 방식이다. 탐색을 진행하다가 하나의 경로가 끝나면 이전 상태로 돌아가 다른 선택지를 다시 탐색한다. 즉, 백트래킹의 핵심은 다음과 같다. 선택 → 탐색 → 선택 취소 → 다른 선택 예를 들어 [1, 2, 3] 을 이용해 순열을 만든다고 생각하면, 1 선택 └─ 2 선택 └─ 3 선택 탐색 완료 ↓ 2 선택 취소 ↓ 3 선택 처럼 이전 선택을 취소하고 다른 경우를 다시 탐색한다. 2. 백트래킹과 DFS의 차이 DFS(Depth First Search)는 한 방향으로 최대한 깊게 들어가며 탐색하는 탐색 방식 이다. 백트래킹은 DFS를 이용해 하나의 선택을 탐색한 뒤, 탐색이 끝나면 이전 상태로 되돌아가 다른 선택을 시도하는 문제 해결 방식 이다. DFS = 한 방향으로 깊게 탐색 백트래킹 = 선택 → 깊게 탐색 → 선택 취소 → 다른 선택 DFS 역시 탐색이 끝나면 이전 노드로 돌아온다. 하지만 백트래킹에서는 단순히 탐색 위치만 돌아가는 것이 아니라, 탐색 전에 변경했던 상태까지 원상복구 한다는 점이 중요하다. 3. 가지치기(Pruning) 백트래킹 과정에서 현재 선택이 정답으로 이어질 가능성이 없다고 판단되면, 해당 경로를 더 이상 탐색하지 않을 수 있다. 이것을 가지치기(Pruning) 라고 한다. 현재 경로 ↓ 정답 가능성 없음 ↓ 더 이상 탐색하지 않음 가지치기를 사용하면 모든 경우를 끝까지 확인하지 않아도 되기 때문에 탐색 횟수를 크게 줄일 수 있다. 백트래킹과 가지치기는 같은 개념은 아니다. 백트래킹 = 탐색 후 이전 상태로 돌아가는 것 가지치기 = 가능성이 없는 경로를 탐색하지 않는 것 4. 백트래킹 알고리즘 절차 백트래킹은 일반적으로 다음과 같은 과정으로 진행된다. 상태 공간 트리를 DFS 방식으로 탐색한다. 현재 선택이 유망한지 확인한다. 유망하다면 다음 단계로 탐색한다. 유망하지 않다면 해당 경로의 탐색을 중단한다. 탐색이 끝나면 이전 상태로 돌아가 다른 선택지를 탐색한다. 여기서 유망하다 는 것은 현재 선택을 계속 이어갔을 때 정답이 될 가능성이 있다는 의미이다. 5. 대표 문제 - N-Queen N-Queen은 N × N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다. 퀸은 다음 방향으로 이동할 수 있다. 같은 열 왼쪽 대각선 오른쪽 대각선 따라서 새로운 퀸을 놓을 때 이 세 방향에 다른 퀸이 존재하는지 검사해야 한다. 8-Queen N = 8 인 경우 가능한 배치의 개수는 92개 이다. # 입력 8을 줌 n = int(input()) vertical = [0] * n seven = [0] * (2 * n) five = [0] * (2 * n) count = 0 def backtracking(level): global count if level == n: count += 1 return for j in range(n): # 같은 열 확인 if vertical[j] == 1: continue # 대각선 확인 if seven[level + j] == 1 or five[level - j + n] == 1: continue vertical[j] = 1 seven[level + j] = 1 five[level - j + n] = 1 backtracking(level + 1) # 이전 상태로 복구 vertical[j] = 0 seven[level + j] = 0 five[level - j + n] = 0 backtracking(0) print(count) 출력 6. 코드에서 각 개념 구분하기 N-Queen 코드에는 완전탐색, DFS, 가지치기, 백트래킹이 모두 들어 있다. 완전탐색 for j in range(n): 현재 행에서 퀸을 놓을 수 있는 모든 열을 하나씩 확인한다. 즉, 가능한 선택지를 전부 시도한다. DFS backtracking(level + 1) 현재 행에 퀸을 놓은 뒤 다음 행으로 넘어가 깊게 탐색한다. 가지치기 if vertical[j] == 1: continue if seven[level + j] == 1 or five[level - j + n] == 1: continue 이미 다른 퀸의 공격 범위에 있는 위치라면 해당 경우는 정답이 될 수 없으므로 탐색하지 않는다. 백트래킹 vertical[j] = 0 seven[level + j] = 0 five[level - j + n] = 0 현재 선택에 대한 탐색이 끝나면 퀸을 놓기 전 상태로 원상복구한다. 이후 반복문에서 다음 위치를 선택해 다시 탐색한다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.39

Уверенность

49%