[백준] 15663 : N과 M(9) (백트래킹) - JAVA

solved ac (실버2)

https://www.acmicpc.net/problem/15663

 

# 문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

 

# 예제

입력 : 

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

3 1
4 4 2

 

출력 : 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

2
4

 

# 필요개념

 

해당 문제는 DFS를 이용한 백트래킹으로 풀어야 하는 문제이다. 중복되는 수열의 출력을 막기 위해서는, 정렬된 형태가 좋고 사전순으로 출력해야하기 때문에 오름차순 정렬을 해주어야 한다. 이때, 수열을 다 만들어놓고 정렬을 하면 복잡해지기 때문에, 입력을 받은 직후에 정렬한 후, 정렬된 수를 이용해 수열을 만드는게 좋다.

 

for문을 이용해 입력받은 수를 순회하면서 dfs로 탐색한다. 탐색하는 조건은 방문하지 않았던 인덱스여야 하고, 이전 값과 다른 값이어야 한다. 같은 값이라면 중복이 되기 때문에 방문하지 않는다 !

 

# Code

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

public class Main {
    static int[] input;
    static boolean[] isVisit; // 방문 인덱스 저장
    static int[] output;
    static int N;
    static int M;

    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());


        input = new int[N];
        isVisit = new boolean[N];
        output = new int[M];

        st = new StringTokenizer(br.readLine());

        for (int i = 0 ; i < N ; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(input);

        dfs(0);
    }

    private static void dfs(int length) {
        if (length >= M) {
            for (int i = 0 ; i < M ; i++) {
                System.out.print(output[i] + " ");
            }
            System.out.println();
        } else {
            int before = 0;
            for (int i = 0 ; i < N ; i++) {
                if (!isVisit[i] && input[i] != before) {
                    isVisit[i] = true;
                    output[length] = input[i];
                    before = input[i];
                    dfs(length + 1);
                    isVisit[i] = false;
                }
            }
        }

    }
}

 

# 결과