BOJ15650 N과 M (2)

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

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

고려해야 할 점

• 1부터 N까지 자연수 중에서 중복 없이 M개를 골라야 한다.
• 고른 수열은 오름차순이어야 한다.
• 중복되는 수열은 여러 번 출력하면 안된다.

중복 없이 선택

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

수열은 오름차순이다

수열을 오름차순으로 만들기 위해서는 수열을 만들기 위한 숫자 배열이 정렬되어 있어야 한다. 여기서 제공된 숫자 배열은 1 ~ n사이의 숫자이기 때문에 이전에 선택한 숫자 이후 부터 탐색을 진행하면 수열이 오름차순임을 보장한다.

위와 같은 상황을 만들기 위해 추가적인 변수가 필요하다. 아래 코드를 살펴보면 start가 해당 역할을 진행하고 있다.

제출 코드

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

public class BOJ15650 {
    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, 1, new int[m]);

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

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

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

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

#BOJ #백트래킹