N 과 M (1)
문제 설명
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
제한 사항
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
4 4
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
푸는 과정에서의 오류
DFS로 풀며 메인 함수에서 선언한 answer 배열과 check 배열을 파라메터로 넘기는 형식으로 dfs 메소드를 구현했습니다. 재귀과정중 한 재귀과정이 끝나고 answer 배열과 check 배열이 재귀과정이 끝나기 전 상태로 돌아가야하는데 그러지 않았습니다..(answer배열을 인자로 넘겼으니, 재귀가 돌아가면 초기화되야되는게 맞는거같은데..) check 배열을 false로 바꿔주는 코드를 작성해서 풀었습니다.
배운점
소스코드
package NandM;
import java.util.*;
public class NandM {
private static int n,m;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=0;i<n;i++) {
int[] answer = new int[m];
boolean[] check = new boolean[n];
int count = 0;
dfs(answer,count,check,i);
}
}
public static void dfs(int[] answer,int count,boolean[] check,int index) {
answer[count] = index+1;
check[index] = true;
count++;
if(count == m) {
for(int i=0;i<answer.length;i++) {
System.out.print(answer[i] + " ");
}
System.out.println();
return;
}
for(int i=0;i<n;i++) {
if(check[i] == true) continue;
dfs(answer,count,check,i);
check[i] = false;
}
}
}