[백준_15654번] N과 M (5)

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

[문제]

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

• N개의 자연수 중에서 M개를 고른 수열입력

 

[입력 조건]

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_15654 {
	static int n,m;
	static int[] num, print;
	static boolean[] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		num=new int[n+1];
		print=new int[n+1];
		visited=new boolean[n+1];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		Arrays.sort(num); // 예제와 같이 출력하기 위해 정렬된 배열 사용
		
		dfs(0);
	}
	
	static void dfs(int depth) {
		// 선택된 숫자의 개수가 m개가 됐다면 선택된 숫자 출력
		if(depth==m) {
			for(int i=0;i<depth;i++) {
				System.out.print(print[i]+" ");
			}
			System.out.println();
			return;
		}
		
		// 백트래킹
		for(int i=1;i<=n;i++) {
			// 이전에 선택되지 않은 숫자라면
			if(!visited[i]) {
				visited[i]=true; // 방문처리
				print[depth]=num[i]; // 숫자 저장
				dfs(depth+1); // 깊이를 1 증가하고 재귀호출
				visited[i]=false; // 재귀호출이 끝난다면 배열 값 되돌리기
			}
		}
	}
}

 

[고찰]

 이번 문제는 백트래킹 연습문제인 N과 M 5번째 문제이다. 이전에 1~4까지 풀었을 때는 매번 다른 사람의 코드를 참고했지만 이후 여러 백트래킹 문제를 풀어오면서 익숙해져서인지 이번 문제는 쉽게 스스로 해결할 수 있었다.