#백준_1062 가르침 - Java 자바

# 유형 : 탐색, 브루트포스, dfs, 문자열, 시뮬레이션

# 문제를 이해하는게 참 어려웠다..

# 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 에서 우선 5개의 알파벳을 사용한다. 따라서 K가 5 보다 작은 값이 들어온다면 읽을 수 없다. 그리고 K가 26이라면 모든 단어를 읽을 수 있다.

만약 K가 6이라면,  a,n,t,i,c 5개를 제외한 알파벳 21개의 알파벳 중 1개를 배웠을 때 주어진 문자열을 읽을 수 있는 최대 경우의 수를 구하는 문제이다. 따라서 백트래킹을 이용하여 탐색하는 방식으로 문제를 접근한다면 어렵지 않게 해결할 수 있다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1062 {
    static int N,K;
    static int max = 0;
    static boolean visit[] = new boolean[26];
    static String[] stArr;
    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());
        stArr = new String[N];
        //남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.  a n t i c
        if(K<5) {
            System.out.println(0);
            return;
        }else if(K==26) { 
            System.out.println(N);
            return;
        }else {
            for(int n=0; n<N; n++) {
                String str = br.readLine();
                stArr[n] = str.substring(4, str.length()-4);
            }
            K-=5;
            visit['a'-97]=true;
            visit['n'-97]=true;
            visit['t'-97]=true;
            visit['i'-97]=true;
            visit['c'-97]=true;
            dfs(0, 0);
            System.out.println(max);
        }
        
    }
    private static void dfs(int start, int count) {
        // TODO Auto-generated method stub
        if(count == K) {
            int rs = 0;
            for(int i=0; i<N; i++) {
                boolean isTrue = true;
                for(int j=0; j<stArr[i].length(); j++) {
                    if(!visit[stArr[i].charAt(j)-97]) {
                        isTrue = false;
                        break;
                    }
                }
                if(isTrue) {
                    rs++;
                }
            }
            max = Math.max(max, rs);
            return;
        }
        
        for(int i=start; i<26; i++) {
            if(!visit[i]) {
                visit[i]=true;
                dfs(i, count+1);
                visit[i]=false;
            }
        }
    }
}