백준 JAVA11 15649번 : N과 M (1)

N과 M (1)

백준 15649번 상세보기

문제

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

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

Flow.

• 순열 을 구하는 문제이다.
• 입력 받은 자연수 범위 N과 순열의 길이 M에 맞추어, 값들을 담을 배열 arr과 방문 여부를 체크할 visited 배열을 초기화 한다.
• DFS를 호출한다. DFS의 매개변수로는 N, M, 현재 탐색 깊이 depth
• 재귀 깊이가 주어진 길이(M)에 도달하면, 탐색 과정에서 선택한 숫자들을 배열에 담아 출력하고 함수를 종료한다.
• 재귀적으로 탐색하며, 선택할 수 있는 숫자 중에서 방문하지 않은 수를 선택한다. 이후, 방문 여부를 체크하고, 해당 숫자를 배열 arr에 담는다.
• 이미 선택한 숫자는 다시 선택하지 않도록 방문 여부 체크
• 재귀 깊이가 주어진 길이(M)에 도달하면, 탐색 과정에서 선택한 숫자들을 배열에 담아 출력한다.

Code.

package backTracking;

import java.util.Scanner;

public class P15649 {
	static int[] arr;
	static boolean[] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 1부터 N까지 자연수 
		int M = sc.nextInt(); // 수열의 길이 M 
		
		arr = new int[M]; //값을 담을 배열 
		visited = new boolean[N];
		dfs(N, M, 0);
	}
	
	public static void dfs(int N, int M, int depth) {
		//재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
		if(depth == M) {
			for(int v : arr) {
				System.out.print(v + " ");
			}
			System.out.println();
			return;
		}
		for(int i = 0; i < N; i++) {
			if(!visited[i]) {
				visited[i] = true;
				arr[depth] = i + 1;
				dfs(N, M, depth + 1);
				visited[i] = false;
			}
		}
	}

}