[BOJ 15649 N과M(1)]

N과M(1)

> 문제 풀이

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열.
출력 예시를 보고 떠오른 생각은 DFS방식의 depth와 방문 배열을 이용하여 재귀 형태로 푸는 것인데 depth는 M, 배열의 크기는 N이다. 가장 어려운 부분이 재귀 함수를 짜는 부분 이므로 생각을 많이 하고 짜야 한다. 재귀 형태의 함수는 함수 종료 지점이 명확해야 한다.

> 프로그램 코드(java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ15649_N과M1 {
	static int N, M;
	static boolean[] visited;
	static int[] a; // 실제 출력값을 담을 배열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");// temp에 " "을 기준으로 String을 나눠 담음.
		N = Integer.parseInt(temp[0]); // String을 int로 변환 후 담음.
		M = Integer.parseInt(temp[1]);

		visited = new boolean[N + 1];
		a = new int[N + 1];
		dfs(1);
	}

	static void dfs(int depth) {
		if (depth == M + 1) {// 종료 지점
			for (int i = 1; i <= M; i++) {
				System.out.print(a[i] + " ");
			}
			System.out.println();
			return;
		}

		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				a[depth] = i;
				dfs(depth + 1);
				visited[i] = false;
			}
		}
	}
}