[백준] 15649 - N과 M (1) (자바/Java) 백트래킹 DFS

문제

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

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

입력

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

출력

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

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

---

이 문제는 백트래킹을 활용한 문제이다.

그 중에서도 DFS를 활용하여 문제를 풀었다. 

먼저 방문 여부를 체크할 check 배열을 만들고, 결과를 담을 result 배열을 만들었다.

cnt가 0부터 시작해서 M이 될 때까지 dfs를 계속하는데, 방문되지 않은 노드를 만날 때마다 result배열에 담고 cnt를 1씩 증가시킨다.

그리고 재귀적으로 dfs가 끝나면, 다시 그 노드의 check를 false로 바꾼다. 이유는 다음 예시를 통해 확인할 수 있다

 

만약 N이 4고 M이 2라면 dfs는 다음 과정을 반복한다.

1 방문

      2 방문 -> 1 2 출력 / dfs end

      3 방문 -> 1 3 출력 / dfs end

      4 방문 -> 1 4 출력 / dfs end

이때 1에서 시작한 수열은 모두 끝이났지만, 2 3 4를 false로 바꿔주지 않는다면 조합의 모든 경우의 수를 출력할 수 없다.

(1 2)와 (2 1)은 다른 수열이기 때문에 dfs가 끝날 때마다 각 노드를 false로 바꿔야 한다.

package BOJ0801;

import java.util.Scanner;

public class BOJ_15649_NandM {
	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값에 대입
				dfs(N, M, cnt + 1); // 다시 재귀적으로 dfs (cnt 1 증가)
				check[i] = false; // i를 false로
			}
		}

	}

}