[PS] 인프런 강의 - DFS 6. 순열 구하기

문제

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

 

▣ 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

 

▣ 입력예제 1
3 2
3 6 9

 

▣ 출력예제 1
3 6
3 9
6 3
6 9
9 3
9 6

 

풀이

기본적으로 중복 순열과 푸는 법은 비슷하지만, 중복을 허용하지 않기 때문에 숫자 사용 여부를 저장할 배열 ch가 필요하다.

 

for(int i=0; i<n; i++) {
   if(ch[i] == 0) {
   	pm[L] = num[i]; //자연수 선택

   	ch[i] = 1; //방문 표시
   	DFS(L+1);
   	h[i] = 0; //돌아왔으면 방문 해제
   }
}

 

여기서 L은 경우의 수를 저장 해둘 pm 배열을 순회하는 인덱스로, DFS 함수의 파라미터로 사용되고

i는 자연수 값이 저장되어있는 num 배열을 순회하는 인덱스이며 ch 배열의 인덱스와 동시에 쓰인다.

 

중복여부 확인후,  pm[L] 에 자연수값을 넣고,

 

DFS 함수 호출 전에 사용 여부를 저장해놨다가, 호출이 끝나고 돌아오면 해제를 해줘야 다음 턴을 이어나갈 수 있다.

 

중복 순열 문제의 예제로 그렸던 트리가 다음과 같이 변경된다.

 

 

코드

import java.util.Scanner;

public class Main {

    static int n, m;
    static int[] num, pm, ch;

    public static void DFS(int L) {
        if(L == m) {
            for(int x : pm) System.out.print(x +" ");
            System.out.println();
        }
        else {
            for(int i=0; i<n; i++) {
                if(ch[i] == 0) {
                    pm[L] = num[i]; //자연수 선택

                    ch[i] = 1; //방문 표시
                    DFS(L+1);
                    ch[i] = 0; //돌아왔으면 방문 해제
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt(); //3~10, 자연수 개수
        m = in.nextInt(); //m개 뽑는다
        num = new int[n];
        ch = new int[n]; //중복 방지를 위한 방문 체크
        pm = new int[m]; //경우의 수 저장해뒀다가 출력할 배열


        for(int i=0; i<n; i++) {
            num[i] = in.nextInt(); //자연수
        }

        //m개 뽑아 일렬로 나열하는 방법 모두 출력
        DFS(0);

    }
}