[백준] 1062번 가르침 (JAVA)

문제

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

설명

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.

따라서, 'a', 'c', 'i', 'n', 't'는 반드시 배워야 하는 글자이다.

현재 배운 글자 수를 selectedCount 라 하고 초기값으로 5로 설정한다.

알파벳 개수만큼 원소로 하는 visited 배열을 만들어 'a', 'c', 'i', 'n', 't'에 해당하는 값은 true로 설정한다.

selectedCount = 5;

visited = new boolean[26];
visited['a' - 'a'] = true;
visited['c' - 'a'] = true;
visited['i' - 'a'] = true;
visited['n' - 'a'] = true;
visited['t' - 'a'] = true;

입력받은 단어들 앞과 뒤에 붙어있는 "anta"와 "tica"는 제외하고 진행한다.

words = new String[N];
for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	words[i] = st.nextToken().replaceAll("[acint]", "");
}

26개의 알파벳 중 방문하지 않은 글자를 시작으로 DFS을 진행한다.

for (int start = 0; start < 26; start++) {
    if (!visited[start])
        dfs(start);
}

시작 노드부터 방문하지 않은 노드를 순차적으로 순회하면서 selectedCount가 K가 되는 순간에 읽을 수 있는 단어의 최댓값을 구한다. countReadable()는 총 몇 개의 단어를 읽을 수 있는지 확인하는 함수이다.

static void dfs(int index) {
    // 1. 체크인
    visited[index] = true;
    selectedCount++;

    // 2. 목적지인가?
    if (selectedCount == K) {
    	max = Math.max(max, countReadable());
    }
    else {
    	// 3. 연결된 곳을 순회
        for (int i = index + 1; i < 26; i++) {
            // 4. 갈 수 있는가?
            if (!visited[i]) {
            	// 5. 간다
            	dfs(i);
            }
        }
    }

    // 6. 체크아웃
    visited[index] = false;
    selectedCount--;
}

static int countReadable() {
    int count = 0;
    for (int i = 0; i < N; i++) {
        boolean flag = true;
        String word = words[i];
        for (int j = 0; j < word.length(); j++) {
            if (!visited[word.charAt(j) - 'a']) {
                flag = false;
                break;
            }
        }

        // 단어를 이루는 모든 글자를 배웠을 경우
        if (flag)
            count++;
    }

    return count;
}

 

전체 코드

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

public class Main {

    static int N, K, max, selectedCount;
    static boolean[] visited;
    static String[] words;

    // 총 몇 개의 단어를 읽을 수 있는지 확인
    static int countReadable() {
        int count = 0;
        for (int i = 0; i < N; i++) {
            boolean flag = true;
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                if (!visited[word.charAt(j) - 'a']) {
                    flag = false;
                    break;
                }
            }

            // 단어를 이루는 모든 글자를 배웠을 경우
            if (flag)
                count++;
        }

        return count;
    }

    static void dfs(int index) {
        // 1. 체크인
        visited[index] = true;
        selectedCount++;

        // 2. 목적지인가
        if (selectedCount == K) {
            max = Math.max(max, countReadable());
        }
        else {
            // 3. 연결된 곳을 순회
            for (int i = index + 1; i < 26; i++) {
                // 4. 갈 수 있는가?
                if (!visited[i]) {
                    // 5. 간다
                    dfs(i);
                }
            }
        }

        // 6. 체크아웃
        visited[index] = false;
        selectedCount--;
    }

    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());
        
        max = 0;
        selectedCount = 5;

        visited = new boolean[26];
        visited['a' - 'a'] = true;
        visited['c' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;

        words = new String[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            words[i] = st.nextToken().replaceAll("[acint]", "");
        }

        // 'a', 'c', 'i', 'n', 't' 는 무조건 가르쳐야 한다.
        if (K < 5)
            System.out.println(0);
        else if (K == 5)
            System.out.println(countReadable());
        else if (K == 26)
            System.out.println(N);
        else {
            for (int start = 0; start < 26; start++) {
                if (!visited[start])
                    dfs(start);
            }
            System.out.println(max);
        }
    }
}