[BOJ 1062] 가르침 (java)

1. 문제 : https://www.acmicpc.net/problem/1062

 

2. 풀이

완전탐색 (백트래킹) 문제임을 알았지만 구현이 어려웠다.

탐색 대상이 나와있는 단어가 아니라 모든 알파벳이라고 생각했다면 좀 더 진전이 있었을 수도..

 

for문을 돌며 dfs를 재귀로 구현하는 방법이 중요했다. (이렇게되면 모든 경우의 수를 다 따질 수 있다.)

 

주어진 K만큼 알파벳을 다 방문하면 (count == K)

단어를 하나씩 돌면서 각 단어의 철자가 visted 표시가 된 알파벳인지 확인한다.

만약 다 방문된 철자라면 rs값을 올려주고

최대값과 비교해주면서 max value를 업데이트!

 

3. 코드

import java.util.*;

class Main {
    static int N,K;
    static int max = 0;
    static boolean visit[] = new boolean[26];
    static String[] arr;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();

        arr = new String[N];

        if(K<5) {
            System.out.println(0);
            return;
        }else if(K==26) {
            System.out.println(N);
            return;
        }else {
            for (int i = 0; i < N; i++) {
                String str = scanner.next();
                arr[i] = 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) {
        if(count == K) {
            int rs = 0;
            for(int i=0; i<N; i++) {
                boolean isTrue = true;
                for(int j=0; j<arr[i].length(); j++) {
                    if(!visit[arr[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;
            }
        }
    }
}