[백트래킹] N과 M(3)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

이 문제는 그냥 다! 나올 수 있는 모든 것을 출력하는 문제이다. 

즉 중복도 괜찮다는 뜻이다!

 

  1) 1 ~ N 까지의 수를 조합한다.

  2) M 개를 선택하여 조합한다. (길이(깊이)가 M이다)

  3) 중복해서 조합 할 수 있다.

 

 

https://st-lab.tistory.com/116

[백준] 15651번 : N과 M (3) - JAVA [자바]

void DFS(int depth) {
	 
	if(depth == M) {//깊이가 최대 깊이일경우 더이상 탐색할 자식노드는 없으므로 return해준다.
		return;
	}
    
	for(int i = 1; i <= N; i++) { //깊이를 1씩 증가시키면서 DFS를 재귀호출한다.
		// 만약 추가 조건이 있다면 반복문 안에 추가하면 된다.
		DFS(depth + 1);
	}
}

 

1 부터 N까지 M의 길이로 조합할 수 있는 조합을 오름차순으로 나열만 하면 되는 문제기에

import java.io.*;
import java.util.*;

public class Main{
    
    public static int[] arr;
    public static int N,M; //N과 M을 전역변수로 선언해준다. 
    //그래야지 bfs 함수에서도 자유롭게 사용가능!
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String args[])throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[M];
        dfs(0);
        System.out.println(sb);
        
    }
    
    public static void dfs(int depth){
    
         //깊이가 최대 깊이일경우 더이상 탐색할 자식노드는 없으므로 return해준다.
        if(depth == M){
            for(int i=0;i<M;i++){
            //arr[i]를 sb에 append해준다.
                sb.append(arr[i]).append(' ');
                
            }
            sb.append('\n');
            return;
        }
        //깊이를 1씩 증가시키면서 DFS를 재귀호출한다.
        //값을 넣으려면 1부터 시작해야함
        for(int i=1;i<=N;i++){
            arr[depth]=i;
            dfs(depth+1);
        }
    }
}

사실 매우 간단하게 짤 수 있다.