알고리즘 풀이 - 백준 1062(가르침, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

남극에 사는 선생님이 학생들에게 단어를 가르치는데, K개의 알파벳만 가르칠 수 있을 때, 전체 문자 중 가르칠 수 있는 문자의 최대 개수를 구하는 문제

 

 

2. 풀이

 

이 문제는 재귀를 통해 간단히 해결할 수 있다. 가르칠 수 있는 모든 알파벳의 경우를 체크하여 가르쳤을 때, 이해 가능한 모든 단어의 개수를 구하는 문제이다.

 

가르칠 알파벳을 26 크기의 배열로 저장하거나 비트마스크를 사용하여 해결할 수 있다. 간단한 문제이므로 코드를 통해 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 완전 탐색 사용(Boolean 배열 이용)

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

public class Main{
    static int n;
    static int k;
    static String[] words;
    static boolean[] alp = new boolean[26];
    static int max = 0;
    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());
        k = Integer.parseInt(st.nextToken());
        words = new String[n];
        
        // 26개의 알파벳을 가르칠 수 있다면 n개의 모든 단어를 가르칠 수 있다.
        if(k == 26) {
            System.out.println(n);
            System.exit(0);
        // 5개 미만이라면 anta, tica 조차 가르칠 수 없으니 0개가 된다.
        } else if(k < 5){
            System.out.println(0);
            System.exit(0);
        }
        
        for(int i=0; i < n; i++){
            words[i] = br.readLine();
        }
        
        // anta, tica에서 무조건 사용되는 값들은 true 처리
        alp['a' - 'a'] = true;
        alp['n' - 'a'] = true;
        alp['t' - 'a'] = true;
        alp['c' - 'a'] = true;
        alp['i' - 'a'] = true;
        
        bruteforce(0, 0);
        System.out.println(max);
        br.close();
    }
    
    private static void bruteforce(int now, int start){
        // 현재 지정된 단어의 수가 k-5개인 경우 배울 수 있는 단어를 찾는다.
        if(now == k-5){
            int learn = 0;
            for(String word : words){
                boolean isValid = true;
                for(int i=0; i < word.length(); i++){
                    // 각 단어의 알파벳이 true가 아니라면 가르치지 않은 내역임
                    if(!alp[word.charAt(i) - 'a']){
                        isValid = false;
                        break;
                    }
                }
                // 배울 수 있는 경우
                if(isValid) learn++;
            }
            // 최대값 갱신
            max = Math.max(max, learn);
            return;
        }
        
        // 각 단어를 가르침
        for(int i=start; i < 26; i++){
            if(alp[i]) continue;
            alp[i] = true;
            bruteforce(now+1, i+1);
            alp[i] = false;
        }
    }
}

 

② 완전 탐색 사용(비트마스크 사용)

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

public class Main{
    static int n;
    static int k;
    static int[] words;
    static int max = 0;
    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());
        k = Integer.parseInt(st.nextToken());
        words = new int[n];
        
        // 26개의 알파벳을 가르칠 수 있다면 n개의 모든 단어 가르칠 수 있다.
        if(k == 26) {
            System.out.println(n);
            System.exit(0);
        // 5개 미만의 알파벳이라면 0개 가르칠 수 있다.
        } else if(k < 5){
            System.out.println(0);
            System.exit(0);
        }
        
        // 각 단어를 비트로 저장한다.
        for(int i=0; i < n; i++){
            String w = br.readLine();
            for(int j=0; j < w.length(); j++){
                char v = w.charAt(j);
                words[i] |= 1 << (v-'a');
            }
        }
        
        // 각 알파벳의 비트를 저장
        int alp = 0;
        alp |= 1 << ('a' - 'a');
        alp |= 1 << ('n' - 'a');
        alp |= 1 << ('t' - 'a');
        alp |= 1 << ('c' - 'a');
        alp |= 1 << ('i' - 'a');
        
        bruteforce(0, 0, alp);
        System.out.println(max);
        br.close();
    }
    
    // now는 현재 가르친 알파벳 숫자, 시작할 알파벳 index
    // flag는 현재까지 가르친 알파벳을 비트로 저장한 내역
    private static void bruteforce(int now, int start, int flag){
    
        // k-5개를 모두 가르쳤다면
        if(now == k-5){
            int learn = 0;
            for(int word : words){
                // word의 모든 단어가 이미 가르친 알파벳인 경우
                if((word | flag) == flag){
                    learn++;
                }
            }
            max = Math.max(max, learn);
            return;
        }
        
        for(int i=start; i < 26; i++){
            // 가르치지 않은 알파벳인 경우에만 수행
            if((flag & 1<<i) == 0){
                bruteforce(now+1, i+1, flag | 1 << i);
            }
        }
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.