1. 백트래킹 알고리즘 : 해를 찾는 도중에 막히면 되돌아가서 다시 해를 추적해나가는 방법. 되추적(Backtracking)이라고 부른다. 가능한 모든 방법을 탐색하는 것에는 깊이 우선 탐색(Depth First Search)가 있는데, 이는 가능한 모든 곳을 방문하기 때문에 경우에 따라 매우 비효율적일 수 있다. 백트래킹은 해를 찾아가는 도중, 현재 경로가 해가 될 것 같지 않으면 그 경로를 계속 가지 않고 되돌아간다. 따라서 비효율적인 경로를 차단하여 고려하지 않는 효율적인 기법이다. 이를 가지치기(pruning)라고 하는데, 가지치기를 얼마나 잘하느냐에 따라 백트래킹 알고리즘의 효율성이 결정된다.
가지치기(pruning) : 경로를 진행하다 해가 될 가능성이 없다고 판단하면 백트래킹(Backtracking)하여 그 노드의 이전(부모노드)으로 되돌아간 후 다음 경로를 진행하는 것.
2. 예제) N-Queen
| N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. |
Queen은 체스에서 다음과 같이 x 표시한 위치로 이동 가능한 기물이다. Queen이 위치한 좌표를 (1,1)이라고 하면, (2,1), (2,2) 등 x표시가 된 좌표는 퀸을 놓을 수 없는 위치이다. (2,3), (3,2) 등은 퀸을 놓을 가능성이 있는 위치이다. 만약 dfs를 한다면 모든 좌표의 지점을 검사하여 수많은 연산을 했겠지만, 백트래킹의 핵심은 가지치기에 있으므로 가능성이 없는 위치는 검사하지 않도록 해야한다.
수행 과정
dfs 수행 -> 퀸을 놓을 수 있는 노드인지 확인(상하좌우, 대각선 같은 줄에 위치하지 않는지) -> 불가능한 노드라면 퀸을 놓지 않고 백트래킹 수행, 상위노드로 다시 이동 / 가능한 노드라면 퀸을 놓음. 현재 놓은 퀸이 N번째 퀸이라면 경우의 수 증가. 해당 노드를 기준으로 dfs 수행하여 다음 퀸의 위치를 찾음.
https://stritegdc.tistory.com/42
[c++] 백준 9663 N-Queen
백준 단계별로 풀어보기 [백트래킹] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을..
stritegdc.tistory.com
'알고리즘 공부 및 문제 풀이 > 알고리즘(ALGORITHM)' 카테고리의 다른 글
| [알고리즘] 최단 경로 알고리즘(3) - 플로이드 워셜(Floyd-Warshall) 알고리즘 (0) | 2022.10.25 |
|---|---|
| [알고리즘] 최단 경로 알고리즘(2) - 다익스트라(Dijkstra) 알고리즘 (0) | 2022.10.25 |
| [알고리즘] 최단 경로 알고리즘(1) - 벨만 포드(Bellman Ford) 알고리즘 (0) | 2022.10.25 |
| [알고리즘] 세그먼트 트리(Segment Tree) (0) | 2022.06.20 |
| [알고리즘] 동적프로그래밍(Dynamic programming) (0) | 2021.07.21 |
