[정리] 백트래킹

백트래킹

• 해를 찾는 도중 해가 아니어서 막히게 되면, 되돌아가서 다시 해를 찾는 기법이다.
• 다시 되돌아가며 경우의 수를 줄이는 방법을 가지치기한다고 말하며, 얼마나 가지치기를 잘하냐에 따라서 효율성이 결정된다.

문제와 코드를 통해서 알아보겠다

• 백준 (15649번) N과 M(1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

풀이

package BackTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class NM1 {
    static boolean[] check;
    static void permu(int[] tmp,StringBuilder sb, int level,int m){
        if(level == m){
            System.out.println(sb.toString());
            return;
        }
//        if 조건으로 백트래킹 을 한다.
        for(int i = 0;i<tmp.length;i++){
            if(check[i])
                continue;
            check[i] = true;
            if(level == 0){
                permu(tmp,sb.append(tmp[i]),level+1,m);
                sb.setLength(sb.length()-1);
            }else{
                permu(tmp,sb.append(" "+tmp[i]),level+1,m);
                sb.setLength(sb.length()-2);
            }
            check[i] = false;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] tmp = new int[n];
        check= new boolean[n];

        for(int i = 0;i<n;i++) tmp[i] = i + 1;

        permu(tmp,new StringBuilder(),0,m);
    }
}