백트래킹
Updated:
백트래킹
문제제시 : N-Queen 문제
- n * n 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제
- 어떤 두 Queen도 서로를 위협하지 않아야 한다.
- Queen을 배치한 n개의 위치는?
- 완탐에서 출발. 단, 처리하는 단계마다 중간중간 체크를 한다.
- 퇴각검색
- 모든 조합을 시도해서 문제의 해를 찾는다.
- 해를 얻을 때까지 모든 가능성을 시도한다.
- 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지(선택지)중에 해결책이 있다.
- 여러 가지(선택지)들이 존재하는 상황에서 하나의 가지를 선택한다.
- 선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
- 이런 선택을 반복하면서 최종 상태에 도달한다.
- 보통 재귀 함수로 구현된다.
당첨 리프 노드 찾기
- 루트에서 갈 수 있는 노드를 선택한다.
- 꽝 노드까지 도달하면 최근의 선택으로 되돌아와서 다시 시작한다.
- 더 이상의 선택지가 없다면 이전의 선택지로 돌아가서 다른 선택을 한다,
- 루트까지 돌아갔을 경우 더 이상 선택지가 없다면 찾는 답이 없다,
8-Queens문제
- 퀸 8개를 크기 8의 체스판 안에 서로를 공ㄱ역할 수 없도록 배치하는 모든 경우를 구하는 문제
- 후보 해의 수 : 64C8
- 실제 해의 수 : 이 중에서 실제 해는 92개뿐
- 즉, 44억 개가 넘는 후보 해의 수 속에서 92개를 최대한 효율적으로 찾아내는 것이 관건.
- 루트 노드에서 리프 노드까지의 경로는 해답후보가 되는데, 완전 탐색을 하여 그 해답후오 중에서 해답을 찾을 수 있다.
- 그러나 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율적이다.
백트래킹 기법
- 모든 후보를 검사? No!
- 백트래킹 기법
- 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다.
- 유망하다 : 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 있으면 유망하다고 한다.
- 가지치키 : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.
- 백트래킹을 이용한 알고리즘은 다음과 같은 절차로 진행된다.
- 상태 공간 트리의 깊이 우선 검색을 실시한다. (재귀적 구현: 함수호출스택)
- 각 노드가 유망한지를 점검한다.
- 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다른 노드로의 검색을 계속한다.
- 일반 백트래킹 알고리즘
backtrack(node v) //현재 상태가 유망한지 유망하지 않는지 체크 IF promising(v) == false then return; IF there is a solution at v write the solution ELSE FOR each child u of v // 가능한 선택지 backtrack(u)
백트래킹과 완전탐색(DFS)와의 차이
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 거 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임(Pruning 가지치기)
- 완전 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다.
- 완전 탐색을 가하기에는 경우의 수가 너무나 많다.
- 예를 들어, N!가지의 경우의 수를 가진 문제에 대해 완전 탐색을 가하면 당연히 처리 불가능한 문제
- 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만, 이 역시 최악의 경우에는 여전히 지수함수시간을 요하므로 처리 불가능할 수 있다.
- 위의 4-Queens문제에서 같은 행에 퀸을 두지 않는 방식의 깊이 우선 탐색(155노드 탐색) vs 백트래킹(27노드 검색)
- 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는것.
- 답이 될 만한지 판단하고 그렇지 않으면, 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것.
- 주로 문제 풀이에서는 DFS로 모든 경우의 수를 탐색하는 과정에서, 조건으로 답이 절대로 될 수 없는 상황을 정의하여 체크하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.
N-Queen 백트래킹 코드
- 첫번째 방법(갔다가 유효검사후 돌아오는 방법)
import java.util.Scanner;
//같은 행에 두지 않는 방식
//N개의 퀸을 위협적이지 않게 놓는 모든 경우의 수
public class NQueenTest2 {
static int N;
static int col[];
private static int cnt;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
col = new int[N+1];
setQueens(1); //1행부터 놓는 시도
System.out.println(cnt);
}
private static void setQueens(int rowNo) {
// 유망여부 체크 : rowNo - 1행까지 유망한지 체크
if(!isAvailable(rowNo-1)) return;
if(rowNo>N) {
//마지막 행까지 다 둔 경우
cnt++;
return;
}
// 현재 퀸 1열부터 N열까지 놓아보기
// 놓았으면 다음 퀸 놓으러 가기
for (int i = 1; i <=N; i++) {
col[rowNo] = i; //i열에 높아보기
setQueens(rowNo+1);
}
}
private static boolean isAvailable(int rowNo) {//rowNo : 현재 검사하려는 퀸
for(int k = 1; k<rowNo; k++) {//k : 이전퀸
if(col[rowNo] == col[k] || Math.abs(col[rowNo] - col[k]) == rowNo - k) return false;
//1. 같은 열에 위치하는지 확인하기
//2. 대각선에 있을시, 행차이와 열차이가 같다.
}
return true;
}
}
- 두번째 방법(가기전에 유효검사하는 방법)
import java.util.Scanner;
//같은 행에 두지 않는 방식
//N개의 퀸을 위협적이지 않게 놓는 모든 경우의 수
public class NQueenTest {
static int N;
static int col[];
private static int cnt;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
col = new int[N+1];
setQueens(1); //1행부터 놓는 시도
System.out.println(cnt);
}
private static void setQueens(int rowNo) {
if(rowNo>N) {
//마지막 행까지 다 둔 경우
cnt++;
return;
}
// 현재 퀸 1열부터 N열까지 놓아보기
// 놓았으면 다음 퀸 놓으러 가기
for (int i = 1; i <=N; i++) {
col[rowNo] = i; //i열에 높아보기
if(isAvailable(rowNo)) {
setQueens(rowNo+1);
}
}
}
private static boolean isAvailable(int rowNo) {//rowNo : 현재 검사하려는 퀸
for(int k = 1; k<rowNo; k++) {//k : 이전퀸
if(col[rowNo] == col[k] || Math.abs(col[rowNo] - col[k]) == rowNo - k) return false;
//1. 같은 열에 위치하는지 확인하기
//2. 대각선에 있을시, 행차이와 열차이가 같다.
}
return true;
}
}
부분집합의 합 문제1
- 유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 몇번이나 있는지를 알아내는 문제.
- 예를 들어, {-7,-3,-2,5,8}라는 집합이 있을 때, {-3,-2,5}는 이 집합의 부분집합이면서 (-3) + (-2) + 5 = 0이므로 이 경우의 답은 참이 된다.
- 완전검색 기법으로 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다.
- 가지치기 불가능
부분집합의 합 문제2
- 유한 개의 자연수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 21이 되는 경우가 몇번이나 있는지를 알아내는 문제
- 예를 들어, {5,21,11,16,6,10}라는 집합이 있을 때, {5,6,10}는 이 집합의 부분집합이면서 5+6+10=21이므로 이 경우의 답은 참이 된다.
- 가지치기 가능 21이 이미 넘었다면 뒤에 가능한 경우의 수는 확인할 필요가 없다.
import java.util.Arrays;
import java.util.Scanner;
import com.sun.org.apache.xml.internal.serializer.ToHTMLSAXHandler;
public class S2_SubSetSumTest2 {
static int N, totalCnt2, totalCnt3, S;
static int[] input;
static boolean[] isSelected;
static int callCnt2, callCnt3;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
S = sc.nextInt();
input = new int[N];
isSelected = new boolean[N];
callCnt3 = callCnt2 = totalCnt2 = totalCnt3 = 0;
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
generateSubset2(0,0);
//가지치기 안한경우
System.out.println("경우의 수 : " + totalCnt2 + "호출횟수" + callCnt2) ;
generateSubset3(0,0);
//가지치기 한경우
System.out.println("경우의 수 : " + totalCnt3 + "호출횟수" + callCnt3) ;
}
private static void generateSubset2(int cnt, int sum) {
//cnt : 부분집합을 처리하기 위해 고려된 원소수
//sum : 기존까지 부분집합 구성원소들의 합.
callCnt2++;
if (cnt == N) {
// 부분집합 완성
// 부분집합의 합 == 목표합 체크
if (sum == S) {
totalCnt2++;
for (int i = 0; i < N; i++) {
if(isSelected[i]) System.out.print(input[i] + " ");
}
System.out.println();
}
return;
}
// 현재 원소를 부분집합에 넣기
isSelected[cnt] = true;
generateSubset2(cnt + 1, sum+input[cnt]);
// 현재 원소를 부분집합에 넣지않기
isSelected[cnt] = false;
generateSubset2(cnt + 1, sum);
}
private static void generateSubset3(int cnt, int sum) {
//cnt : 부분집합을 처리하기 위해 고려된 원소수
//sum : 기존까지 부분집합 구성원소들의 합.
callCnt3++;
// 부분집합의 합 == 목표합 체크
if (sum == S) {
totalCnt3++;
for (int i = 0; i < N; i++) {
if(isSelected[i]) System.out.print(input[i] + " ");
}
System.out.println();
return;
}
if(sum>S || cnt==N) return;
//목표로 하는 값을 넘어버렸을 때. or // 부분집합 완성
// 현재 원소를 부분집합에 넣기
isSelected[cnt] = true;
generateSubset3(cnt + 1, sum+input[cnt]);
// 현재 원소를 부분집합에 넣지않기
isSelected[cnt] = false;
generateSubset3(cnt + 1, sum);
}
}
Leave a comment