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

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

입력

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

 

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며,

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

 

 

N과 M문제(1) 에서 오름차순 조건이 하나 추가된 문제인듯

4 4에서 1 2 3 4 만 가능하다. 

 

 

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

public class Main{
    
    public static int[] arr;
    public static boolean[] visit;
    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());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        arr = new int[m];
        visit = new boolean[n];
        dfs(n,m,0);
        System.out.println(sb);
    }
    
    public static void dfs(int n, int m, int depth){
        if(depth==m){
            Arrays.sort(arr);
            for(int val:arr){
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i=0;i<n;i++){
            if(!visit[i]){
                visit[i]=true;
                arr[depth]=i+1;
                dfs(n,m,depth+1);
                visit[i]=false;
            }
        }
    }
}

나는 Arrays.sort(arr); 한 줄만을 추가했고, 결과는 틀렸습니다...

 

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

[백준] 15650번 : N과 M (2) - JAVA [자바]

 

다만 이 문제의 특징이라하면 N과 M을 입력받으면 "1부터 N까지의 수 중 오름차순이면서

M의 길이까지 나열 가능한 수열"이어야 한다. 

 

이번에는 이전과는 다르게 깊이를 의미하는 depth 변수뿐만 아니라 at 변수를 추가해주었다.

at 변수의 의미는 현재 위치, 즉 어디서부터 시작하는지를 의미하는 변수다.

 

예로들어 반복문에서 재귀를 해 줄 때, at = 1 부터 시작하면 다음 재귀는 오름차순으로 탐색하기 위해

at 을 1 증가시킨 2를 인자로 넘겨주면서 다음 재귀의 반복문이 2부터 시작하도록 하는 변수를 의미한다.

 

 

public static void dfs(int at, int depth) {
		
	if(depth == M) {
		/*
		 깊이가 M이랑 같을경우 출력
		*/
	}
	
	/*
	 i 는 at 부터 탐색하도록 한다.
	*/
	for(int i = at; i <= N; i++) {
		// 현재 깊이를 index로 하여 해당 위치에 i 값을 담는다
		arr[depth] = i;
        
		/*
		 재귀호출 :
		 현재 i 값보다 다음 재귀에서 더 커야하므로
		 i + 1 의 값을 넘겨주고, 깊이 또한 1 증가시켜 재귀호출해준다
		*/
		dfs(i + 1, depth + 1);
	}
	
}

 

그리고 이전 문제와 달리 중복방문인지를 고려할 필요가 없으므로 boolean 배열로 중복 여부를 체크할 필요 또한 없다.

차피 재귀 과정에서 만약 모든 배열에 채우지 못하는 경우에는 depth == M 이 될 수 없게되고,

반복문이 먼저 끝나기 때문에 자동으로 걸러지게 된다.

 

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

public class Main{
    
    public static int[] arr;
    public static int n,m; //n과 m을 전역변수로 선언
    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(1,0);//at=1
        System.out.println(sb);
    }
    
    public static void dfs(int at, int depth){
        if(depth==m){
            for(int val:arr){
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i= at; i<=n;i++){//n과 같을 때까지 
            arr[depth]=i;
            dfs(i+1,depth+1);
            
        }
    }
}