-
백 트래킹 (Backtracking) 이란?Computer Science/Algorithm 2020. 1. 30. 14:21728x90반응형
1. 백 트래킹 (Backtracking)
- 백트래킹 (Backtracking) 또는 퇴각 검색 (Backtrack)으로 불린다.
- 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략
- 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법
- 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현
- 각 후보를 DFS 방식으로 확인
- 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
- Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
- Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)
상태 공간 트리 (State Space Tree)
- 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리
예를들어 a를 시작으로 각 높이의 1개 노드를 연결해 연속 4개를 홀수를 만들고 싶다고 가정하자. a - b - e - h가 전부 홀수라면 가능한 경우이다. 그런데 만약 b가 홀수가 아니라면 이미 a - b 다음에 뭐가 오더라도 조건을 만족하지 못하기 때문에 b 아래는 조사하지 않고 Backtracking 한다는 것이다. 백트래킹으로 유명한 N-Queen문제를 보면서 이해해보자.
2. N Queen 문제 이해
- 대표적인 백트래킹 문제
- NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
- 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 함
체스판을 N x N 체스판을 생각해보자. 퀸은 대각선, 상하좌우를 다 이동할 수 있다. 따라서 4 x 4의 체스판이라면 위와 서로 공격할 수 없는 상태로 만드려면 위와 같이 배치를 해야 한다.
Pruning (가지치기) for N Queen 문제
- 한 행에는 하나의 퀸 밖에 위치할 수 없다. (퀸은 수평 이동이 가능하기 때문이다.)
- 맨 위에 있는 행부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치한다.
- 만약 앞선 행에 배치한 퀸으로 인해, 다음 행에 해당 퀸들이 이동할 수 없는 위치가 없을 경우에는, 더 이상 퀸을 배치하지 않고, 이전 행의 퀸의 배치를 바꿈
- 즉, 맨 위의 행부터 전체 행까지 퀸의 배치가 가능한 경우의 수를 상태 공간 트리 형태로 만든 후, 각 경우를 맨 위의 행부터 DFS 방식으로 접근, 해당 경우가 진행이 어려울 경우, 더 이상 진행하지 않고, 다른 경우를 체크하는 방식
예를들어 4 x 4 체스판(1행 ~ 4행, 1열 ~ 4열)에서 가장 먼저 1행 1열에 퀸을 놓았다고 생각해보자. 그러면 2행1열과 2행 2열은 놓을 수가 없다.(2행 1열은 같은 열이고, 2행2열은 대각선이기 때문) 따라서 2행에서 1열을 놓고 그 다음인 3행과 4행을 볼 필요가 없다 (왜냐하면 2행이 이미 놓을 수 없는 곳이기 때문이다) 이렇게 위의 과정을 반복해서 경우의 수를 찾으면 된다.
위의 말이 이해가 되지 않는다면 이렇게 상태공간트리를 보면 이해가 될 것이다. 맨 처음에 (0, 1)을 놓았다면
(1, 0), (1, 1), (1, 2)는 놓을 수 없기 때문에 그 밑에 서브트리는 확인할 필요가 없고 (1, 3)을 시작으로 하는 것만 찾으면 된다.
Promising for N Queen 문제
- 해당 루트가 조건에 맞는지를 검사하는 기법을 활용하여,
- 현재까지 앞선 행에서 배치한 퀸이 이동할 수 없는 위치가 있는지를 다음과 같은 조건으로 확인
- 한 행에 어차피 하나의 퀸만 배치 가능하므로 수평 체크는 별도로 필요하지 않음
위의 개념을 알고 있어야 코드를 구현하는데 많은 도움이 된다. 퀸을 현재 자리에 놓을 수 있는지 없는지를 체크하는 과정이다. 수직체크는 같은 열인지 확인하는 것이기 때문에 열끼리 뺀 것의 절대값이 1이라면 같은 열이다.
그리고 대각선체크는 행끼리 뺀 값 == 열끼리 뺀 값이 성립한다면 대각선의 위치이기 때문에 놓을 수 없다.
코드 구현 with Java
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.util.Scanner;public class NQueen {public static int N;public static int count;public static void main(String[] args) {Scanner input = new Scanner(System.in);N = input.nextInt();for (int i = 1; i <= N; ++i) {int[] col = new int[N + 1];// 인덱스 0은 쓰지 않음col[1] = i; // N x N 체스판에서 1행1열 ~ 1행 N열 까지 하나 씩 놓으면서 경우의 수 구하기dfs(col, 1);}System.out.println(count);}public static void dfs(int[] col, int row) {if (row == N) {count++; // 1행 1열 ~ 1행 N열 까지 놓을 때 가능한 경우의 수 전부 count} else {for (int i = 1; i <= N; ++i) {col[row + 1] = i; // col[행] = 열 으로 생각 (ex : col[2] = 1 이라면 2행 1열 이라는 뜻)if (isPossible(col, row + 1)) {dfs(col, row + 1);}}}}public static boolean isPossible(int[] col, int row) {// 현재 메소드에서 체스를 놓은 행 다음 행에서 놓을 수 있는 자리를 판별해준다.for (int i = 1; i < row; ++i) {if (col[i] == col[row]) return false; // 같은 열 이면 놓을 수 없기 때문에 falseif (Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;// 대각선을 판별하는 조건은 행끼리 빼기 ==}return true; // 대각선도 아니고 같은 열도 아니라면 true}}[강의자료 출처]
https://www.fastcampus.co.kr/dev_online_algo/
반응형'Computer Science > Algorithm' 카테고리의 다른 글
최장 공통 부분 수열(LCS : Longest Common Subsequence)란? (2) 2020.06.21 소수 찾기(에라토스테네스의 체) (0) 2020.02.09 그리디(Greedy) 알고리즘이란? (1) 2020.01.29 동적 계획법 (Dynamic Programming)이란? (0) 2020.01.28 Dijkstra의 최단 경로 알고리즘이란? (0) 2020.01.28