[BOJ] 1062번 가르침 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, K, max = 0;
    static boolean[] used;
    static String[] words;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        init(br);
        process(br);
        print();
    }

    private static void init(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        words = new String[N];
    }

    private static void process(BufferedReader br) throws IOException {
        // 모든 단어는 "anta" 로 시작하고 "tica" 로 시작하므로, 5개의 알파벳 고정
        // K 가 5보다 작으면 어느 글자도 읽을 수 없음
        if (K < 5) {
            max = 0;
        } else if (K == 26) {
            max = N;
        } else {
            // 단어 입력
            for (int i = 0; i < words.length; i++) {
                words[i] = br.readLine();
            }
            K -= 5; // 고정된 알파벳 개수만큼 감소
            used = new boolean[26];
            used['a' - 'a'] = true;
            used['n' - 'a'] = true;
            used['t' - 'a'] = true;
            used['i' - 'a'] = true;
            used['c' - 'a'] = true;
            // 글자 조합 생성
            comb(0, 0);
        }
    }

    private static void comb(int depth, int now) {
        if (depth == K) {
            int cnt = 0;
            for (String word : words) {
                if (isReadable(word)) {
                    cnt++;
                }
            }
            max = Math.max(max, cnt);
            return;
        }
        for (int i = now; i < 26; i++) {
            if (used[i]) continue;
            used[i] = true;
            comb(depth + 1, i);
            used[i] = false;
        }
    }

    private static boolean isReadable(String word) {
        for (int i = 0; i < word.length(); i++) {
            if (!used[word.charAt(i) - 'a']) {
                return false;
            }
        }
        return true;
    }

    private static void print() {
        System.out.println(max);
    }
}

📄 해설

글자 처리에 대한 접근을 놓치면 풀기 어려운 문제.

접근

• 재귀를 이용한 백트래킹 문제
• 알파벳 26자를 방문 표시하기 위한 방문 배열 used 배열을 사용해야함
• 모든 단어는 anta 로 시작하고, tica 로 끝난다는 점을 이용해야함

과정

5개의 글자를 알아야 단어를 한개라도 읽을 수 있으므로, K 의 값이 5보다 작은 경우 답은 0이 된다.

26개의 글자를 안다면 모든 단어를 읽을 수 있으므로 답은 N 이 된다.

5개 이상 26개 미만의 글자를 안다면 재귀를 시작한다. (재귀 시작 전, 방문 배열 used 에 a, n, t, i, c 총 5개의 알파벳은 방문처리를 미리 해둔다.)

• 재귀 과정
  1. 일반적인 재귀 코드. K 번의 재귀가 진행됐다면, 주어진 단어들을 읽을 수 있는지를 확인한다. ( isReadable 메소드)
  2. 각 단어의 글자 중 used 배열에 표시되어있지 않은 글자가 있다면 그 단어는 읽을 수 없다.
  3. isReadable 메소드의 반환값이 true 인 경우는 그 단어를 읽을 수 있는 것이므로, cnt 의 값을 증가시킨다.
  4. 모든 단어의 확인이 끝났으면 최댓값을 갱신한다.

위의 재귀 과정을 수행하고, 재귀가 모두 끝이나면 최댓값을 출력한다.