백트래킹 알고리즘

백트래킹 알고리즘

• 백준15651

1. 백트래킹으로 푸는 문제.

   • 백트래킹이란?
     1. 어떤 노드의 유망성을 판단하여, 해당 노드가 유망하지 않으면
        부모 노드로 돌아가 다른 자식 노드를 찾는 방법.
     2. 즉, 모든 경우의 수를 찾아보지만 가능성이 있는 경우의 수만 찾는 방법
   • 문제의 조건 확인
     1. 1 ~ N 까지의 조합한다.
     2. M개를 선택하여 조합한다.(M이 깊이이다.)
     3. 중복해서 조합할 수 있다.
   • DFS
     1. 대표적 백트래킹 알고리즘 DFS로 구현한다.
     2. 재귀함수를 사용하여 완전탐색 시전.

2. 코드

    package programmers;
   
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
   
    public class Baek15651 {
        static StringBuilder sb = new StringBuilder();
        static int N;
        static int M;
        static int[] selected;
   
        static void recFun(int k) {
            // M개를 전부고르면 return
            // 고르지 못했을 때, k번째부터 M번째 원소를 조건에 맞게 고르기.
            if (k == M) {
                for (int i=0; i<M; i++) sb.append(selected[i]).append(" ");
                sb.append("\n");
            } else {
                for (int i=1; i<=N; i++) {
                    selected[k] = i;
                    recFun(k+1);
                }
            }
        }
        public static void main(String args[]) throws IOException {
            input();
            recFun(0);
            System.out.println(sb.toString());
        }
   
        static void input() 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());
            selected = new int[M];
        }
    }