[JAVA] 백준 15649

 

 

 

15649번: N과 M (1)

문제

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

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

풀이

백트래킹을 통해서 이전 depth에서 고른 번호를 체크하고 다음 depth로 진행하면서 모든 경우를 탐색하였다.

📌 백트래킹 탐색

    public static void DFS(int depth, String value){
        if(depth == M){
            sb.append(value.substring(1)).append("\n");
            return;
        }

        for(int i=1; i<N; i++){
            if(!V[i]) {
                V[i] = true;
                DFS(depth + 1, value + " " + i);
                V[i] = false;
            }
        }

    }

depth가 찾고자하는 자릿수와 같다면 현재 수열을 추가한다. (substring해주는 이유는 첫 자리에 공백을 지우기 위해)

• 백트래킹은 전체 경우의 수에서 가망이 없는 경우를 미리 가지치기 해낸다.
• 내 생각에는 여기서 가지치기 하는 경우는 이미 방문했던 노드를 !V[i]를 통해서 걸러내는 작업이 가지치기에 해당하는 것 같다.

📌 전체 코드

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

class Main {
    static StringBuilder sb =new StringBuilder();
    static boolean[] V;
    static int N;
    static int M;
    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())+1;
        M = Integer.parseInt(st.nextToken());

        V = new boolean[N];

        DFS(0, "");
        System.out.println(sb);
    }

    public static void DFS(int depth, String value){
        if(depth == M){
            sb.append(value.substring(1)).append("\n");
            return;
        }

        for(int i=1; i<N; i++){
            if(!V[i]) {
                V[i] = true;
                DFS(depth + 1, value + " " + i);
                V[i] = false;
            }
        }

    }

}

결과