백준 15649 N 과M(1)

배운점 

오랜만에 백트래킹 문제를 풀어봐서 그런지 생각대로 잘 풀리지않았다. 모든 경우를 다 탐색한다는 것을 염두에 두고 코드를 짜고 return하는 조건에 대해서 잘 생각해봐야겠다.

항상 리커전 문제를 풀때 트리형식으로 먼저 그려보고 코드를 짜는 습관을 가지자!

 

풀이

package 백트래킹;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class N_M1{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] in  = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int m = Integer.parseInt(in[1]);
        boolean[] visit = new boolean[n];
        int[] ar = new int[m];
        fun(n,m,0,visit,ar);
    }
 
    static void fun(int n,int m,int depth,boolean[] vis,int[] ar){
      if(depth==m){  //숫자를 m개 뽑은 경우 출력
         for(int i:ar)
             System.out.print(i+" ");
          System.out.println();
          return;
 
      }
        for (int i = 0; i <n ; i++) { //호출될때마다 0부터  끝까지 방문되었는지 확인
            if(!vis[i]){ //방문되지않은 곳이라면
                vis[i]=true; // 방문 표시
                ar[depth] = i+1; // 배열에 그 데이터 저장
                fun(n,m,depth+1,vis,ar); // 숫자를 하나 뽑았으니까 깊이 1증가
                vis[i] = false; // 다음 호출을 위해 방문표시 지움
            }
        }
 
    }
 
}