[ 백준 15649 ] N과 M (1) ( 자바 )

[ 백준 15649 ] N과 M (1) ( java ) 

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

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

 

 

출처: 백준, https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

 

 

핵심 

가장 기본적인 백트래킹 문제 

 

dfs ( i ) : M자리에서 i 번 째 자리에 1~N 중 하나를 선택한다. 그리고 dfs ( i+1 ) 호출 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드 1

dfs가 만들어지는 결과(ans)를 모두 갖고 다니는 경우 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    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());
        
        visited = new boolean[N+1];
        
        dfs(0, "");
    }
    static int M, N;
    static boolean[] visited ;
    
    static void dfs(int counts, String ans ) {
        
        if(counts == M) {
            System.out.println(ans.substring(1));
            return;
        }
        
        for(int i = 1 ; i <= N ; i++ ) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(counts+1, ans +" "+ i);
                visited[i] = false;
            }
        }
    }
}

 

코드 2

dfs가 만들어지는 결과를 memo[i]에 넣고 백트래킹으로 관리 

( 백트래킹 관점으로 수열 M을 memo[0~M-1]에서 관리 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    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());
        
        memo = new int[M];
        visited = new boolean[N+1];
        
        dfs(0);
        System.out.println(sb.toString());
    }
    static int M, N;
    
    // memo[i]: i 번째에 들어갈 숫자 
    static int[] memo;
    static boolean[] visited;
    
    static StringBuilder sb = new StringBuilder();
    
    static void dfs(int pos ) {
        
        if(pos == M) {
            
            sb.append(memo[0]);
            for(int i = 1 ;  i < M; i++) {
                sb.append(" ");
                sb.append(memo[i]);
            }
            sb.append("\n");
            return;
        }
        
 
        for(int i = 1 ; i <= N ; i++ ) {
            if(!visited[i]) {
                visited[i] = true;
                memo[pos] = i;
                dfs(pos+1);
                visited[i] = false;
            }
        }
    }
}