백준 15650 N과 M(2)

배운점

 예전에 풀고 다시문제를 풀어보았는데 문제를 푸는데 두가지 방법이 있었다. 먼저 첫 번째 방법은 for문을 이용하여 0,1,2,...n-1까지 시작하여 이전에 선택한 숫자보다 1이 큰 숫자부터 for문을 돌려 방문하지 않았다면 선택해주는 방식으로 문제를 풀었다.

 

첫 번째 방법

 

package 백트래킹;
 
import java.io.*;
import java.util.StringTokenizer;
 
public class N과M2 {
    public static void main(String[] args) throws Exception {
        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());
        boolean[] vis = new boolean[n];
        int [] ar = new int[m];
        fun(n,m,0,vis,ar);
    }
    //방법 1
    static void fun(int n,int m,int depth,boolean[] vis,int[] ar){
        if(depth==m){ // 다 뽑은 경우
            for (int i = 0; i <ar.length ; i++) {
                System.out.print(ar[i]+" ");
            }
            System.out.println();
            return;
        }
        int i = 0;
        if(depth>0) i = ar[depth-1]; //깊이가 0이아닌 경우 이전에 선택했던 숫자를 i로 시작
        for (; i <n ; i++) {
            if(i<0) i=0;
            if(!vis[i]){
                vis[i] = true;
                ar[depth] = i+1;
                fun(n,m,depth+1,vis,ar);
                vis[i] = false;
            }
        }
    }
 
  
}
 

 

두번째 방법은 깊이를 증가시킬때 마다 그 깊이와 일치하는 숫자를 선택하지 않는지 이진트리의 형태로 나누어 문제를 해결하였다. 리커전을 탈출하는 경우는 1)깊이가 n까지 다 도달한 경우 2)m가지 숫자를 선택한 경우 로 나누어서 해결하였다.

두 번째 방법

package 백트래킹;
 
import java.io.*;
import java.util.StringTokenizer;
 
public class N과M2 {
    public static void main(String[] args) throws Exception {
        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());
        boolean[] vis = new boolean[n];
        int [] ar = new int[m];
        fun2(n,m,0,vis,ar);
    }
  //방법2    
    static void fun2(int n,int m,int depth,int size,boolean[] vis,int[]ar){
 
        if(m==size){
            for (int i = 0; i <ar.length ; i++) {
                System.out.print(ar[i]+" ");
            }
            System.out.println();
            return;
        }
        if(depth ==n){
            return;
        }
        vis[depth] = true;
        ar[size] = depth+1;
        fun2(n,m,depth+1,size+1,vis,ar);
        vis[depth] = false;
 
        fun2(n,m,depth+1,size,vis,ar);
 
    }
  
}