BOJ15649 N과 M (1)

https://www.acmicpc.net/problem/15649 (opens new window)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구한다.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

고려해야 할 점

• 1부터 N까지 자연수 중 중복 없이 M개를 골라야 한다.
• 수열은 사전 순으로 증가하는 순서로 출력한다.
• 중복되는 수열은 여러 번 출력하면 안된다.

중복 없이 선택

방문 여부를 가지고 있는 boolean 배열을 활용한다. 단순히 중복 없이 M개를 고르는 것이기 때문에 모든 배열을 탐색하며 방문 기록만 확인한다.

사전 순으로 증가하는 순서

간단히 나타내면 오름차순을 의미한다. 현재 주어진 n의 값을 활용하여 수열을 만든다. 즉 1부터 수열을 채우게 되면 자연스럽게 오름차순으로 정렬하게 된다.

제출 코드

아래는 최종 제출 코드이다.

public class BOJ15649 {
    private static int n;
    private static int m;
    private static boolean[] visited;
    private static List<String> results;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        visited = new boolean[n + 1];
        results = new ArrayList<>();

        backtracking(0, new int[m]);

        results.forEach(System.out::println);
    }

    private static void backtracking(int depth, int[] values) {
        if (depth == m) {
            String result = Arrays.stream(values)
                .mapToObj(String::valueOf)
                .collect(joining(" "));
            results.add(result);
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visited[i]) {
                continue;
            }

            visited[i] = true;
            values[depth] = i;
            backtracking(depth + 1, values);
            visited[i] = false;
        }
    }
}

#BOJ #백트래킹