[백준] 15650 - N과 M (2) (자바/Java) 백트래킹 DFS 조합

문제

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

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

입력

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

---

이전 문제와 달라진 점은 전의 문제가 순열이었다면 이번에는 조합을 구하는 경우이다.

조건에 수열이 오름차순이라는 것이 추가되었는데, 이는 즉 1 2 3 4만 허용되고, 1 2 4 3, 1 4 3 2 등은 허용되지 않는 것이니 중복을 허용하지 않겠다는 뜻과 같다.

그래서 수열을 구하는 알고리즘에서 자신보다 큰 원소만 검사할 수 있도록 새로운 매개변수 k를 추가해주었다.

 

dfs를 원래는 1보다 크거나 같고 N보다 작거나 같은 수를 모두 확인하면서 진행하였지만, 이제는 i보다 큰 수에 대해서만 검사하며 자연스럽게 오름차순으로 정렬되도록 하였다.

package BOJ0803;

import java.util.Scanner;

public class BOJ_15650_NandM2 {
	static boolean[] check;
	static int[] result;

	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		check = new boolean[N + 1];
		result = new int[M + 1];

		dfs(N, M, 0, 1);

		System.out.print(sb);

	}

	static void dfs(int N, int M, int cnt, int k) {

		if (cnt == M) { // 배열의 개수가 M이 되면 출력하고 return
			for (int i = 0; i < M; i++) {
				sb.append(result[i] + " ");
			}
			sb.append("\n");
			return;
		}
        
        // k보다 큰 수에만 dfs
		for (int i = k; i <= N; i++) {
			if (!check[i]) { // 방문하지 않은 노드
				check[i] = true; // 방문 체크
				result[cnt] = i; // result값에 대입
				dfs(N, M, cnt + 1, i + 1); // 다시 재귀적으로 dfs (cnt 1 증가)
				check[i] = false;
			}

		}

	}

}