[BOJ 1897] 토달기

문제 링크 : https://www.acmicpc.net/problem/1897

문제

희현이는 원장선생님 말씀에 토를 다는 것을 몹시 좋아한다. 토를 단다는 것은 원장선생님께서 어떤 단어를 말씀하시면 그 단어의 맨 앞이나 중간, 혹은 맨 뒤에 한 글자를 끼워 넣어서 새로운 단어를 만드는 것으로, 버릇없는 행동과는 아무런 관계가 없는 순수한 단어 놀이이다.

희현이는 사전에 등재된 단어만을 사용한다. 사전은 d개의 단어로 구성되어 있으며, 각 단어는 80자 이내의 알파벳 소문자로만 이루어져 있다. 희현이는 원장선생님께서 어떤 단어를 말씀하셨을 때, 한 글자씩 토를 달아 사전에 등재된 단어를 계속 만들어 갈 경우, 가장 긴 단어를 만들려면 어떻게 해야 하는지가 궁금해졌다. 이를 해결하는 프로그램을 작성하라.

입력

첫 줄에 사전에 등재된 단어의 수 d와, 원장님이 처음 말씀하신 단어가 주어진다. (1 ≤ d ≤ 1,000) 원장님이 처음 말씀하신 단어의 길이는 세 글자이며, 사전에 있는 단어를 말씀하셨다. 다음 d개의 줄에는 사전에 등재된 단어가 한 줄에 하나씩 주어진다.

출력

첫 줄에 토달기 규칙을 지키며 단어를 만들어 갈 때, 만들 수 있는 단어 중 가장 긴 것을 출력한다. 답이 여럿일 경우 어느 것이나 상관없다.

제한

시간 제한	메모리 제한
2sec	128MB

힌트

cal, coal, coral, choral, chorale 순으로 단어를 만들어 나가면 된다.

---

풀이

단어의 갯수가 최대 1천개다. $O(N^2)$의 완전 탐색으로도 최대 탐색 횟수는 1백만번. 각 단어의 길이도 최대 $80$이므로 시간 제한 이내에는 충분히 돌아갈 것 같다. 해서, 시작 단어로부터 BFS 탐색을 통해 가장 긴 단어를 찾아내면 된다. BFS의 특성 상 길이가 긴 단어들이 뒤에 나오므로, 큐의 가장 마지막 문자열을 출력해주면 정답을 얻을 수 있다.

BFS 탐색을 위해서는 각 노드들을 정의하고 간선을 정의해야 한다. 노드는 당연히 단어 자체가 될 것이다. 그리고 간선은 글자 하나만 추가하여 만들 수 있는지의 여부로 정의하면 된다. 아래 코드가 그 역할을 수행할 수 있다.

bool only_one_more(int longer_idx, int shorter_idx) {
    char* L = words[longer_idx].str;
    char* S = words[shorter_idx].str;

    bool skipped = false;
    for (int i = 0, j = 0; i < words[longer_idx].length && j < words[shorter_idx].length; ++i, ++j) {
        if (L[i] != S[j]) {
            if (skipped == true) {
                return false;
            } else {
                skipped = true;
                j -= 1;
            }
        }
    }

    return true;
}

이를 활용해 시작 단어로부터 각 단어로 BFS 탐색을 진행하면 답을 얻을 수 있다. 별다른 테크닉은 필요하지 않다.

소스코드

Github Link : Source Code

참고 알고리즘 : BFS 탐색