백트래킹

 

 

 

처음 접했을 때 이해하기 쉽지 않은 알고리즘이다.

 

재귀함수를 활용해 구현하는 경우가 많고, 함수 종료 조건 / 재귀 호출 부분 두 가지를 잘 고려해 함수를 디자인하자.

 

확률과통계 과목에서 수열을 나열하거나, 논리회로나 계산이론 과목에서 accept할 수 있는 언어를 찾을 때 해당하는 수 또는 단어들을 나열할 때 수형도를 사용하는데, 여기서 사용하는 수형도가 백트래킹과 깊게 연관되어있다.

 

 

import java.io.*;
import java.util.*;

public class Main {
	static int N, K;
	static ArrayList<Integer> list = new ArrayList<>();	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		StringTokenizer st = new StringTokenizer(br.readLine());

		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		bt(1);	

	}
	static void bt(int cnt){
		if(cnt == N + 1){
			for(int k : list){
				System.out.print(k + " ");
			}			
			System.out.println();
			
			return;

			
		}

		for(int i=1; i<K+1; i++){
			list.add(i);			
			bt(cnt + 1);
			list.remove(list.size() - 1);			
		}
	}
}

 

 

백트래킹의 기본형인데, 리스트나 배열에 원소를 추가해 준 다음 지우는 과정을 이해할 때 수형도를 직접 그려서 확인해 보는게 가장 효과적이다..

 

일단 백트래킹 알고리즘을 이해하고 나면, 백준이나 타 문제풀이 플랫폼을 이용해 백트래킹 관련 문제를 많이 풀어서 문제유형에 익숙해지고, 백트래킹 코드를 손에 익히자.

 

그래프 탐색이나 그리디 등등.. 여러 알고리즘과 백트래킹이 결합해 하나의 문제로 나타나는 경우가 많다.

 

이런 문제를 풀기 위해서 백트래킹 알고리즘을 직접 짤 수 있어야 한다..

 

백트래킹의 활용으로는 조합, 순열, 뽑기에서 제한두기 등등 여러 가지가 있다.

일단 위의 백트래킹 기본형을 잘 숙지하면 변형문제들은 쉽게 풀 수 있으니 기본형을 제대로 이해하자.

 

기본형만 잘 이해하면 나머지는 사고력 문제 인 것 같다.

 

 

당연히 재귀함수 대신 반복문을 사용해서 백트래킹을 구현할 수도 있지만, 반복문으로 구현하는 경우 고르는 가짓수에 따라 for문을 한없이 사용해야 해서 적합하지 않다.

 

재귀를 배울 때 재귀를 사용하면 코드를 깔끔하게 작성할 수 있는 경우가 종종 있다고 했는데, 백트래킹이 그 예시 중 하나이다..

 

 

관련 문제를 찾아보면 1~N으로 만들 수 있는 수를 M자리 출력... 이런 문제처럼 누가 봐도 백트래킹으로 풀어야 될 것 같은 문제도 있지만, 특수한 문제 상황을 주고 그 상황 속에서 백트래킹을 찾아 내야 하는 경우도 있다.

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    static int N, M, K, score;
    static ArrayList<Integer> list = new ArrayList<>();

    static int[] turn;
    static int[] piece;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        turn = new int[N];
        piece = new int[K];

        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            turn[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<K; i++){
            piece[i] = 1;
        }

        backtracking(0);

        System.out.println(score);

    
    }

    static void backtracking(int cnt){

        score = Math.max(score, cal());
        
        if(cnt == N ){
            return;
        }
        
        for(int i=0; i<K; i++){
            if(piece[i] >= M){
                continue;
            }

            piece[i] = piece[i] + turn[cnt];
            backtracking(cnt + 1);
            piece[i] = piece[i] - turn[cnt];
        }

    }

    static int cal(){
        int local_score = 0;

        for(int i=0; i<K; i++){
            if(piece[i] >= M){
                // System.out.println("sadf");
                local_score++;
            }
        }

        return local_score;
    }
}

 

 

위와 같은 경우..

 

가지치기 개념을 이해하고 많이 연습해보자.