[백준] 15663번 - N과 M (9) (Silver 2)

문제 링크

백준 15663번 - N과 M (9) (Silver 2)

문제 설명

N개의 자연수가 주어졌을 때, 이들 중 M개를 고른 수열을 중복하지 않고 출력하는 문제이다.
N개의 자연수 중 서로 같은 것이 있을 수도 있다.

정답 코드 및 설명

백트래킹을 활용하는 전형적인 문제이다.
주어진 수에 중복이 있을 수도 있다는 점을 처리하는 부분이 조금 까다롭다.
탐색하려는 값이 직전에 탐색한 값과 같으면 스킵하는 방식으로 이를 구현했다.

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

public class Main {

    static int n, m, arr[], seq[];
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        dfs(0);
        print();
    }

    static void input() 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());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);
        seq = new int[m];
        visit = new boolean[n];
    }

    static void dfs(int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++)
                sb.append(seq[i]).append(' ');
            sb.append('\n');
            return;
        }
        for (int i = 0; i < n; i++) {
            if (depth == 0 || !visit[i]) {
                visit[i] = true;
                // 직전에 얻은 수열의 마지막 값이 탐색하려는 값과 같으면 중복이므로 스킵
                if (seq[depth] != arr[i]) {
                    seq[depth] = arr[i];
                    dfs(depth + 1);
                }
                visit[i] = false;
            }
        }
        seq[depth] = 0;
    }

    static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.close();
    }
}