순열 구하기(DFS)

설명

10 이하의 N개의 자연수가 주어졌을 때, 이 중 M개를 뽑아 일렬로 나열하는 모든 경우의 수(순열)를 출력하는 문제이다. 이때 출력은 사전순으로 오름차순으로 정렬된 결과를 제공해야 한다.

 

입력 설명

• 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어진다.
• 두 번째 줄에 N개의 자연수가 오름차순으로 주어진다.

출력 설명

• 첫 번째 줄에 모든 경우의 순열을 출력한다.
• 출력되는 순서는 사전순으로 오름차순이다.

예시 입력

3 2
3 6 9

 

 

예시 출력

3 6
3 9
6 3
6 9
9 3
9 6

 

풀이 과정

1. 입력된 자연수 배열에서 M개를 선택해 순서대로 나열하는 순열을 구한다.
2. DFS(깊이 우선 탐색) 방법을 이용하여 순열을 구하며, 선택된 숫자가 다시 선택되지 않도록 체크 배열을 사용한다.
3. 모든 경우의 순열을 탐색하여 조건을 만족하면 출력한다.

D(0)
├── i = 0 (3)
│   ├── i = 1 (6) -> (3, 6)
│   └── i = 2 (9) -> (3, 9)
├── i = 1 (6)
│   ├── i = 0 (3) -> (6, 3)
│   └── i = 2 (9) -> (6, 9)
└── i = 2 (9)
    ├── i = 0 (3) -> (9, 3)
    └── i = 1 (6) -> (9, 6)

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[] pm, ch, arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);  // N: 자연수 개수
        m = Integer.parseInt(str[1]);  // M: 뽑을 개수

        arr = new int[n];  // 입력된 자연수 배열

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());  // 배열에 자연수 입력
        }

        ch = new int[n];  // 선택 여부 체크 배열
        pm = new int[m];  // 뽑힌 자연수 순열 저장 배열

        DFS(0);  // 깊이 우선 탐색 시작
    }

    public static void DFS(int L) {
        if (L == m) {  // M개를 모두 뽑은 경우 출력
            for (int x : pm) {
                System.out.print(x + " ");
            }
            System.out.println();
        } else {
            for (int i = 0; i < n; i++) {
                if (ch[i] == 0) {  // 해당 숫자가 아직 선택되지 않았다면
                    ch[i] = 1;  // 선택 체크
                    pm[L] = arr[i];  // 현재 위치에 숫자 배치
                    DFS(L + 1);  // 다음 단계로 이동
                    ch[i] = 0;  // 탐색 후 선택 해제 (백트래킹)
                }
            }
        }
    }
}

 

코드 설명

1. 입력된 자연수 배열에서 M개의 숫자를 선택해 순서대로 나열하는 모든 순열을 구한다.
2. ch 배열은 각 숫자가 선택되었는지 여부를 체크하는 배열이다. 중복 선택을 방지한다.
3. DFS 함수를 이용해 깊이 우선 탐색 방식으로 M개의 숫자를 선택하며, 선택이 완료되면 출력한다.
4. 백트래킹을 통해 선택한 숫자를 다시 해제하고, 다른 조합을 탐색한다.

풀이 요약

• 입력된 N개의 숫자 중에서 M개의 숫자를 선택하여 가능한 모든 순열을 구한다.
• 각 단계에서 선택되지 않은 숫자를 선택해 DFS 방식으로 탐색하며, M개가 선택되면 해당 순열을 출력한다.