[완전탐색] BOJ 15654 N과 M (5)

 

15654번: N과 M (5)

 

1) 아이디어

N개의 숫자 중 중복없이 M개를 순서 있게 나열하는 문제이기 때문에 완전탐색의 순열 문제이다. 

 

각 자리에서 재귀호출로 다음 자리로 올 수 있는 모든 경우의 수를 백트래킹으로 탐색하면 된다.

단, 중복을 허용하지 않으므로 visit[]으로 방문처리를 해서 방문안해본 경우만 탐색한다.

 

2) 시간복잡도

순열 문제이므로 O(N^M)인데 N과 M의 최댓값이 8 이므로 O(8^8) < 1억 

 

3) 구현

 

 

// 언어 : JAVA , (성공/실패) : 1/0 ,
// 메모리 : 36276 KB , 시간 : 404 ms

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] num, selected, visit;

    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());
        M = Integer.parseInt(st.nextToken());

        // N개의 자연수 저장
        num = new int[N + 1];

        visit = new int[10001];

        selected = new int[M + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(num);

        rec_func(1);

        bw.close();
    }

    private static void rec_func(int k) throws IOException {
        if (k == M + 1) {
            for (int i = 1; i <= M; i++) {
                bw.write(selected[i] + " ");
            }
            bw.write("\n");
        } else {
            for (int i = 1; i <= N; i++) {
                int n = num[i];

                if(visit[n] == 1) continue;

                selected[k] = n;
                visit[n] = 1;

                rec_func(k + 1);

                selected[k] = 0;
                visit[n] = 0;
            }
        }
    }


}