[백준]15629 N과M(1)

문제

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

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

입력

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

출력

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

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

입출력 예제

입력1 3 1

출력1 1 2 3

입력2 4 4

출력2 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

소스코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		boolean arr[] = new boolean[n];
		int answer[] = new int[k];
		
		recur(arr,answer,0);
	}
	
	public static void recur(boolean arr[],int answer[], int index) {
		if(index==answer.length){
			for(int i=0;i<answer.length;i++) {
				System.out.print(answer[i]+" ");
			}
			System.out.println();
			
		}else {
			for(int i=0;i<arr.length;i++) {
				if(!arr[i]) {
					arr[i]=true;
					answer[index]=i+1;
					recur(arr,answer,index+1);
					arr[i]=false;
				}
			}
		}
	}
}

풀이과정

순열을 구현하는 문제이다. 중복된 숫자가 출력될 수 없으므로 방문 여부를 체크하는 배열(arr)와 방문한 숫자를 출력하기 위한 배열(answer)과 몇개를 방문했는지를 나타내는 변수(index)가 필요하다. 방문하지 않았을 경우 방문여부를 arr배열에 체크해주고(방문한 인덱스를 true로 변경) answer배열에 방문한 숫자를 입력한 뒤, 다시 재귀함수를 호출한다. 조합이 아닌 순열이기 때문에 방문 순서가 달라도 answer에 기록해야 한다. 방문한 후 배열은 다시 원상복구 시켜 나중에 다시 방문하기 위해서 arr배열을 false로 초기화 시켜준다.