무작위로 주어진 수들의 순열,조합 구하기. (백트레킹) 2021-06-10

우선적으로 사용자로부터 N과 M 입력 값을 받는다. 그리고, 연산의 대상이되는 수들을 사용자로부터 N개 입력받는다.

N P M을 구해보겠다.

우선 순열이나, 조합 모두 dfs의 방법중 하나인 백트레킹을 이용한다. 

1.모든 노드를 탐색해야한다.

2.노드 탐색의 조건이 있다.(한번 방문한 노드는 방문하지 않는다.

 

그러므로 dfs를 통한 백트레킹 방법을 이용한다.

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

public class Main {
    static int[] arr;
    static int[] output;
    static boolean[] value;
    static int N;
    static int M;

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
       N=s.nextInt();
       M=s.nextInt();
       arr=new int[N];
       output=new int[M];
       value=new boolean[N+1];
        for (int i = 0; i < N; i++) {
            arr[i]=s.nextInt();
        }
        Arrays.sort(arr);
        dfs(0);
    }
    static void  dfs(int depth){
        if(depth==M){
            for (int i = 0; i < output.length; i++) {
                System.out.print(output[i]+" ");
            }
            System.out.println();
        return;
        }
        else{
            for(int i=0;i<arr.length;i++){
                int now=arr[i];
                if(!value[i]){//각 불규칙적인 now값을 boolean 배열에 담을 수 없으니, 인덱스 값을
                    //boolean값으로 (한번 방문했는지 안했는지 판단 기준)
                    value[i]=true;
                    output[depth]=now;
                    dfs(depth+1);
                    value[i]=false;

                }
            }
        }


    }
}

 

우선 솔직히 말하자면, 처음 백트레킹 관련문제 백준 N과 M 시리즈를 처음풀때는 정말 이해할수가 없었다. 그러나 발현되는( 수들중 M개를 고른 조합)을 도출하는 과정을 노드의 깊이로 보고, 그 깊이가 다 찼을때, 주어진 output 배열을 출력해주면 된는 원리를 알게 되었다. 또한 한번 방문했던 수는 value 함수를 통해 true / false 처리로 다시 방문 안하게끔 만들어주었기 때문에, 순열이나 조합 모두 한번방문했던 노드는 방문하지 않는다는 특징을 지킬수있다.

그리고 한번 방문했던 노드들을 M만큼 깊이를 다 채우고 return되면 다시 false로 풀어주고 큰 for문의 변수 i가 증가되기 때문에, 다음번에는 재방문할수 있다. 즉, 3 P 2 를 1 2 3에 적용시킨다 가정하면,

1 2 까지 output배열이 찼을때(이 때, i의 값은 1) 프린트된다음, retrun을 통해 다시 원래 호출한 함수로 돌아와서, 1이랑 2를 다시 false로 (방문 가능한 상태)로 맞추어놓고, 과정을 다시 진행한다. 그럼 다음 순서는 2 1 이렇게 output배열이 채워진다. 2 2는 안됨 이유: 2를 한번 방문했으니까. 마찬가지로 첫번째 for루프 돌때도, 1 1은 안됨.

 

다음은 조합을 구하는 코드를 작성해 보겠다.

public class Main {
    static int[] arr;
    static int[] output;
    static boolean[] value;
    static int N;
    static int M;

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
       N=s.nextInt();
       M=s.nextInt();
       arr=new int[N];
       output=new int[M];
       value=new boolean[N+1];
        for (int i = 0; i < N; i++) {
            arr[i]=s.nextInt();
        }
        Arrays.sort(arr);
        dfs(0,0);
    }
    static void  dfs(int depth,int at){
        if(depth==M){
            for (int i = 0; i < output.length; i++) {
                System.out.print(output[i]+" ");
            }
            System.out.println();
        return;
        }
        else{
            for(int i=at;i<arr.length;i++){
                int now=arr[i];
                if(!value[i]){//각 불규칙적인 now값을 boolean 배열에 담을 수 없으니, 인덱스 값을
                    //boolean값으로 (한번 방문했는지 안했는지 판단 기준)
                    value[i]=true;
                    output[depth]=now;
                    dfs(depth+1,i+1);
                    value[i]=false;

                }
            }
        }


    }
}

 

여기서 N P M 순열을구하는 코드랑 차이점은, 바로 for문에 at이라는 변수를 하나 추가하는 것이다. 이유는 조합은 순열과 달리, 순서를 고려하지 않기에, 다시 앞전의 값을 쓸 필요가 없다. 그래서 새로운 for문의 시작점을 매 dfs함수의 재귀호출마다 설정해 주어서 순서를 허용하지 않게 만드는 것이다.