백트레킹

백트레킹

백트래킹의 핵심 아이디어

• 문제를 풀기 위해 가능한 모든 경우를 탐색하지만, 불필요한 경우는 미리 제외(가지치기)하여 효율성을 높인다.

• 재귀적 탐색: 현재 단계에서 해를 구성하고, 다음 단계로 넘어가며 재귀적으로 해를 확장한다.

• 조건 검사(가지치기, Pruning): 현재 경로가 문제의 조건을 만족하지 않으면 탐색을 중단하고 이전 단계로 돌아간다.

백트래킹의 구조

• 종료 조건: 탐색을 멈추는 조건을 정의

• 가능한 후보 생성: 현재 상태에서 선택 가능한 모든 후보를 생성

• 가지치기(Pruning): 현재 선택이 유망하지 않다면(조건을 만족하지 않는다면) 탐색을 중단하고 다음 후보로 넘어간다/

• 재귀 호출: 유망한 후보에 대해 다음 단계로 재귀 호출

• 백트래킹: 모든 후보를 처리한 뒤에는 현재 선택을 취소하고 이전 단계로 돌아간다.

백트래킹 알고리즘의 일반적인 형태

function backtrack(현재 상태):
    if (종료 조건 만족):
        정답 처리
        return

    for (각 후보 in 가능한 후보들):
        if (해당 후보가 조건에 맞는지 검사):
            후보 선택
            backtrack(다음 상태) # 재귀 호출
            후보 선택 취소 (백트래킹)

예시1 (N-Queen)

public class Main {
    static int N;
    static int[] board;
    static int count = 0;
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
        board = new int[N];
        countNum(0);
        System.out.println(count);
    }
    
    static void countNum(int row){
        if(row == N){
            count++;
            return;
        }
        for(int i=0; i<N; i++){
            board[row] = i;
            if(isPassed(row)){
                countNum(row+1);
            }
        }
    }
    
    static boolean isPassed(int row){
        for(int i=0; i<row; i++){
            if(board[row] == board[i] || row - i == Math.abs(board[row] - board[i])){
                return false;
            }
        }
        
        return true;
    }
}

예시2 (좋은 수열)

public class Main {
    static int N;
    static boolean found = false;
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
        back("");
    }
    
    static void back(String str){
        if(found){
            return;
        }
        
        if(str.length() == N){
            System.out.println(str);
            found = true;
            return;
        }
        
        for(int i=1; i<=3; i++){
            if(isPassed(str+i)){
                back(str+i);
            }
        }
    }
    
    static boolean isPassed(String str){
        int len = str.length();
        for(int i=1; i<=len/2; i++){
            if(str.substring(len-i).equals(str.substring(len-2*i, len-i))){
                return false;
            }
        }
        return true;
    }
}