완전 탐색 기초

1) 완전 탐색

- 완전 탐색이란 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법입니다. 

  그 중에서도 백트레킹(back-tracking)을 통해 문제를 해결할 수 있어야 합니다. 

  

2) 완전 탐색을 할 때 주의할 점

- 완전 탐색은 함수의 정의가 50%입니다. 백트레킹의 경우는 크게 4개의 케이스로 나눠지는데

  (1) N개 중 중복을 허용해서 M개를 순서 있게 나열하기

  (2) N개 중 중복없이 M개를 순서 있게 나열하기

  (3) N개 중 중복을 허용해서 M개를 고르기

  (4) N개 중 중복없이 M개를 고르기

  입니다. 

 

(1) N개 중 중복을 허용해서 M개를 순서 있게 나열하기

15651번: N과 M (3) (acmicpc.net) 

import java.util.*;

public class Main {
    
    static int N;
    static int M;
    static int[] selected; 
    static StringBuilder sb; 
    
    public void recursive(int k){
        
        if(k == M+1){
            for(int i=1; i<=M; i++){
                sb.append(selected[i]).append(' ');
            }
            sb.append('\n');
            return; 
        }
        
        for(int i=1; i<=N; i++){
            selected[k] = i;
            recursive(k+1);
            selected[k] = 0;
        }    
        
    }
    
    public static void main(String args[]) {
    
      Scanner sc = new Scanner(System.in);
      sb = new StringBuilder(); 
      Main T = new Main();  
      
      N = sc.nextInt();
      M = sc.nextInt();
      
      selected = new int[N+1]; 
      
      T.recursive(1);
      
      System.out.println(sb.toString());
      
    }
}

 

(2) N개 중 중복없이 M개를 순서 있게 나열하기

15649번: N과 M (1) (acmicpc.net)   

import java.util.*;

public class Main {
    
    static int N;
    static int M;
    static int[] selected; 
    static boolean[] check; 
    static StringBuilder sb; 
    
    public void recursive(int k){
        
        if(k == M+1){
            for(int i=1; i<=M; i++){
                sb.append(selected[i]).append(' ');
            }
            sb.append('\n');
            return; 
        }   
        
        for(int i=1; i<=N; i++){
            if(check[i] == true) continue;
            
                check[i] = true;
                selected[k] = i;
                recursive(k+1);
                selected[k] = 0;
                check[i] = false; 
            
        }
    }

    public static void main(String args[]) {
    
      Scanner sc = new Scanner(System.in);
      sb = new StringBuilder(); 
      Main T = new Main();  
      
      N = sc.nextInt();
      M = sc.nextInt();
      
      check = new boolean[N+1];
      selected = new int[N+1]; 
      
      T.recursive(1);
      
      System.out.println(sb.toString());
      
    }
}

 

(3) N개 중 중복을 허용해서 M개를 고르기

15652번: N과 M (4) (acmicpc.net)

import java.util.*;

public class Main {
    
    static int N;
    static int M;
    static int[] selected; 
    static StringBuilder sb; 
    
    public void recursive(int k){
        
        if(k == M+1){
            for(int i=1; i<=M; i++){
                sb.append(selected[i]).append(' ');
            }
            sb.append('\n');
            return; 
        }
        
        int start = selected[k-1];
        if(start == 0) start = 1;
        
        for(int i=start; i<=N; i++){
                selected[k] = i;
                recursive(k+1);
                selected[k] = 0;
            
        }
    }
    

    public static void main(String args[]) {
    
      Scanner sc = new Scanner(System.in);
      sb = new StringBuilder(); 
      Main T = new Main();  
      
      N = sc.nextInt();
      M = sc.nextInt();
      
      selected = new int[N+1]; 
      
      T.recursive(1);
      
      System.out.println(sb.toString());
      
    }
}

 (4) N개 중 중복없이 M개를 고르기

 

 

import java.util.*;

public class Main {
    
    static int N;
    static int M;
    static int[] selected; 
    static StringBuilder sb; 
    
    public void recursive(int k){
        
        if(k == M+1){
            for(int i=1; i<=M; i++){
                sb.append(selected[i]).append(' ');
            }
            sb.append('\n');
            return; 
        }
        
        int start = selected[k-1];
        
        for(int i=start+1; i<=N; i++){
                selected[k] = i;
                recursive(k+1);
                selected[k] = 0;
            
        }
    }
    

    public static void main(String args[]) {
    
      Scanner sc = new Scanner(System.in);
      sb = new StringBuilder(); 
      Main T = new Main();  
      
      N = sc.nextInt();
      M = sc.nextInt();
      
      selected = new int[N+1]; 
      
      T.recursive(1);
      
      System.out.println(sb.toString());
      
    }
}

 

- 결론적으로 완전 탐색 문제를 접근할 때는, 

   (1) 고를 수 있는 값의 종류를 파악하고,

   (2) 중복을 허용하는지

   (3) 순서가 중요한지 

   파악해야 합니다.

 

 

참고

한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online