[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합

N과 M은 순열, 조합, 중복순열, 중복조합을 연습할 수 있는 문제이다.

순열과 조합은 재귀를 사용하여 풀 수 있다.

 

1. 순열

순열에서 nPr은, N개의 수에서 가능한 r개의 수를, 순서대로 나열하는 것이다. 순열에는 순서가 존재하기 때문에 1 2 3과 3 2 1은 다른 경우로 취급한다.

이를 재귀와 dfs를 활용하여 풀면 다음과 같다.

cnt는 dfs의 깊이를 의미한다. cnt가 M이 되면 M개의 순열이 완성되었다는 의미이므로 함수를 return 한다.

또한 순열은 중복을 허용하지 않기 때문에 순열에 포함되었는지 여부를 확인할 boolean check 배열이 필요하다.

배열의 처음부터 for문을 돌며 방문하지 않은 노드일 경우 check를 true로 바꾸고, 다시 깊이 cnt를 +1 한 다음, 재귀적으로 dfs를 반복한다.

또 중요한 것은, dfs가 끝나면 check를 false로 바꿔야 한다는 것이다.

이 과정을 반복하면 cnt가 M이 될 때마다 하나의 순열이 출력되고, 다시 이전 과정으로 돌아가 다음 순열을 구하는 방법을 반복한다.

import java.util.Scanner;

public class Main {
	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);
		System.out.print(sb);

	}

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

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

	}

}

---

2. 조합

조합은 순열과 유사하지만, 순서가 없는 경우를 의미한다. 즉 수의 조합을 오름차순으로 출력한다고 이해하면 된다.

1 2 3과 2 1 3은 같은 경우이기 때문에, 오름차순인 1 2 3 만 가능한 경우의 수로 포함한다.

코드에서 순열과 다른 부분은 k라는 매개변수가 추가된 것이다. 

방문하지 않은 노드를 체크하는 것은 동일하지만, depth가 증가할 때마다 for문을 탐색할 때 이전 값인 i보다 큰 값부터 탐색을 시작해야 한다.

import java.util.Scanner;

public class Main {
	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;
		}
		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;
			}

		}

	}

}

---

3. 중복순열

중복순열은 좀 더 간단하다. 방문 여부를 체크할 필요가 없고, 처음부터 for문을 돌리며 차례대로 추가하면 된다.

package BOJ0812;

import java.util.Scanner;

public class BOJ_15651_N과M3 {
	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();
		int[] out = new int[M];
		perm(N, out, 0, M);
		System.out.print(sb.toString());

	}

	static void perm(int N, int[] out, int depth, int r) {

		if (depth == r) {

			for (int i = 0; i < out.length; i++) {
				sb.append(out[i] + " ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 1; i <= N; i++) {
			out[depth] = i;
			perm(N, out, depth + 1, r);

		}
	}

}

---

4. 중복조합

중복 조합은 중복순열을 오름차순으로 출력한 것과 같다.

중복순열을 구하는 과정에서 start 변수만 추가하여 오름차순으로 배열에 값을 추가하면 된다.

package BOJ0812;

import java.util.Scanner;

public class BOJ_15652_N과M4 {
	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();
		int[] out = new int[M];
		comb(N, out, 1, 0, M);
		System.out.print(sb.toString());

	}

	static void comb(int N, int[] out, int start, int depth, int M) {
		if (depth == M) {
			for (int i = 0; i < out.length; i++) {
				sb.append(out[i] + " ");
			}
			sb.append("\n");
			return;
		}

		for (int i = start; i <= N; i++) {
			out[depth] = i;
			comb(N, out, i, depth + 1, M);
		}
	}

}