순열

문제

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

 

입력

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

 

입력 예시

3 2

3 6 9

 

출력 예시 

3 6 

3 9

6 3

6 9

9 3

9 6 

 

 

풀이과정 

 

반복문과  DFS를 이용하여 순열을 구현할 수 있다. 

static int n,m;
static int[] arr;
static boolean [] visited;
static int[] answer;

• 첫번째 줄에 주어진 자연수들을 저장하기 위한 배열 arr을 선언한다. 
• 중복으로 선택되는것을 막기 위해 boolean 배열을 이용하여 한번 선택되었다면 방문처리를 해준다. 
• 선택된 수를 저장하기 위해 answer 배열을 사용하여 기록한다. 

 

main 코드 

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

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

    arr = new int[n];
    answer = new int[m];
    visited = new boolean[n];


    st = new StringTokenizer(br.readLine());
    for(int i=0;i<n;i++){
        arr[i] = Integer.parseInt(st.nextToken());
    }

    dfs(0);
}

• N개를 저장할 배열들을 만들고 초기화 한다. 
• M개의 숫자를 저장할 수 있는 배열을 초기화 한다. (answer 배열은 마치 경로를 기록하는 용도)
• 이후 반복문을 이용해 주어진 숫자들을 배열에 저장하고 dfs 함수를 호출한다. 

 

 

dfs 코드 

static void dfs(int L){
    if(L==m){
        for (int x : answer) {
            System.out.print(x+" ");
        }
        System.out.println();
    }else{
        for(int i=0;i<n;i++){
            if(!visited[i]){
                answer[L]=arr[i]; // 경로기록
                visited[i]=true; // 방문처리
                dfs(L + 1);
                visited[i]=false;
            }
        }
    }
}

 

 

 

if(L==m){
    for (int x : answer) {
        System.out.print(x+" ");
    }
    System.out.println();
}

• 만약 호출 횟수가 m과 같아진다면, 재귀호출을 멈추고 지금까지 answer배열에 저장된 값들을 출력한다. 

 

else{
    for(int i=0;i<n;i++){
        if(!visited[i]){
            answer[L]=arr[i]; // 경로기록
            visited[i]=true; // 방문처리
            dfs(L + 1);
            visited[i]=false;
        }
    }
}

• 아직 호출의 횟수가 m번 미만이라면, 재귀호출을 반복한다. 
• 반복문을 통해 arr 배열을 탐색하며 아직 방문하지 않은 곳을 선택한다. 
• 이때 경로를 기록하고 선택된 인덱스 값이, 재귀호출 이후에 또 다시 선택되는것을 막기위해 방문처리한다. 
• 재귀호출이 끝난 이후에는 다시 방문 할 수 있도록 방문 처리했던 것을 취소해준다. 

 

 

전체코드 

package 섹션8_DFS_BFS심화;

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

public class Q6_순열구하기 {

    static int n,m;
    static int[] arr;
    static boolean [] visited;

    static int[] answer;

    static void dfs(int L){
        if(L==m){
            for (int x : answer) {
                System.out.print(x+" ");
            }
            System.out.println();
        }else{
            for(int i=0;i<n;i++){
                if(!visited[i]){
                    answer[L]=arr[i]; // 경로기록
                    visited[i]=true; // 방문처리
                    dfs(L + 1);
                    visited[i]=false;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        arr = new int[n];
        answer = new int[m];
        visited = new boolean[n];


        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);
    }
}