23.07.08 - 23.07.10 공부 (트라이)

백준의 '단계별로 풀어보기' 41단계에서 등장하는 트라이(Trie) 파트를 공부했다. 개념, 구현은 바킹독 블로그를, 추천 문제는 단계별로 풀어보기 41단계와 바킹독 블로그(아래 링크 참고)를 참고했다. (아래 사용하는 chk 배열 등의 용어는 바킹독 블로그의 내용을 따름.)
https://blog.encrypted.gg/1059

1. 백준 14725번 - 개미굴

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

14725번: 개미굴

트라이 기본 문제..라고는 하는데 기본까지는 잘 모르겠다.

트라이를 고정 배열(알파벳 26개 할당)로 만들지 않고 벡터로 선언한다. 트라이로 문자열을 삽입할 때, 트리를 타고 내려가면서 해당 노드의 벡터를 순회한다. 그 벡터에 삽입할 문자열이 있는지 없는지를 검사하며 트라이를 구성한다.

트라이 구성이 완료되면, dfs를 돌려 출력 형식에 맞게 출력해주면 된다. 사전 순서가 앞서도록 해야 하므로 다음 노드를 탐색하기 전, 현재 노드의 문자열 벡터를 정렬해주어야 한다.

2. 백준 5670번 - 휴대폰 자판(원. Cellphone Typing)

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

5670번: 휴대폰 자판

첫 번째 난관. 여러가지가 꼬여 몇 번 틀리다가 AC받은 문제.

별도의 cnt 배열을 도입한다. 이 배열은 $i$번 노드에 대하여 이 노드의 다음 글자 종류가 총 몇 개인지를 저장하는 배열이다. 따라서 트라이를 구성할 때, 다음 노드가 없는 경우(-1로 저장되어있는 경우) 그 새로운 노드에 대한 cnt 배열값은 1이 될 것이고, 만약 다음 노드가 이전과 다른 종류의 글자(알파벳)이라면 그 노드에 대한 cnt 배열값은 1 증가할 것이다. (물론 이전에 사용된 종류의 알파벳이라면 cnt 배열값은 그대로이다.)

이제 이 cnt 배열로 휴대폰 자판을 치는 횟수를 구하여 보자. 첫 글자는 무조건 쳐야 하므로 단어의 개수만큼은 무조건 휴대폰 자판을 쳐야 한다. 또, 현재 노드의 cnt 배열이 2 이상이라면 휴대폰 자판을 쳐야 한다.

그러나 cnt 배열이 1이어도 휴대폰 자판을 쳐야 하는 경우가 있다. abc와 abcdef가 있다고 하자. 처음 a를 치고 나서 abc까지는 자동입력이 되지만, 입력하고자 하는 문자열이 abcdef일 경우 d를 한 번 더 쳐야 온전한 문자열을 입력할 수 있다. 따라서 1) cnt 배열 값이 1이지만, 2) 어떤 문자열의 끝이면서, 3) 아직 온전한 문자열이 입력된 상태가 아니라면 이때에도 입력 횟수를 1 증가시켜야 한다.

참고로 테스트 케이스마다 주어지는 단어 길이의 총합이 $10^6$이므로 고정 배열로 트라이를 구성해도 상관없다. (이걸 못 봐서 몇 번 MLE가 났다..)

3. 백준 14426번 - 접두사 찾기

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

14426번: 접두사 찾기

이 문제야말로 트라이를 연습하기에 가장 기초 문제가 아닐까 하는 생각이 든다.

트라이로 $N$개의 문자열을 삽입한 뒤, 그 트라이에서 $M$개의 각각의 문자열을 찾을 수 있는지를 확인한다. 별도의 chk 배열을 둘 필요 없이, 다음 노드 번호가 -1인지 아닌지만 검사하면 쉽게 해결할 수 있다.

4. 백준 5052번 - 전화번호 목록(원. Phone List)

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

5052번: 전화번호 목록

한 문자열이 다른 문자열의 접두사가 되는지 안 되는지를 확인하면 된다.

확인을 쉽게 하기 위해서, 문자열 목록을 길이의 오름차순으로 정렬하고, 그 후 트라이를 구성한다.

트라이로 문자열을 삽입할 때, 어떤 노드의 chk 배열(바킹독 문제집 참고)이 true일 경우 문자열 목록이 일관성 없는 목록임을 알 수 있다. 왜냐하면 chk가 true라는 것은 그 문자열이 이미 전에 삽입되었고, 따라서 그 문자열이 현재 삽입하고자 하는 문자열의 접두사임을 의미하기 때문이다.

5. 백준 16934번 - 게임 닉네임

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

16934번: 게임 닉네임

chk 배열을 bool 배열이 아닌 int 배열로 선언한다.
트라이의 다음 노드에 -1 값이 저장되어 있다면 지금까지의 문자열의 접두사를 별칭으로 사용한다. 트라이 구성을 여기서 끝내지 않고, 문자열의 끝까지 삽입하도록 한다. 마지막 글자 노드에 대하여 chk 배열값을 1 증가시킨다.

만약 문자열을 끝까지 삽입하였는데도 별칭을 만들지 못하였다면, 원래의 닉네임과 chk 배열값을 붙여서 만들면 된다.

별도의 set 자료구조 등을 사용하지 않고, 한 번의 트라이 구성만으로도 해결할 수 있기 때문에 이 풀이가 깔끔한 풀이라는 생각이 든다.

6. 백준 9202번 - Boggle

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

9202번: Boggle

시간제한이 10초라지만, 단순 dfs로 풀 경우 쉽게 시간초과가 난다. 트라이를 활용한다는 것만 안다면, 나머지 구현에 모든 힘을 쓰면 되는 문제.

단어 사전에 등재되어 있는 단어들에 대하여 트라이를 구성한다. 다음, 4x4 보드판의 각 칸에 대하여 완전탐색을 시작한다. 이때, 무작정 완전탐색을 하는 것이 아닌 트라이를 타고 내려가면서 다음 글자가 있는지를 확인하여야 한다.

..물론 여기서 끝이 아니고, 단어 사전에 있는 문자열을 발견했다면, 문제에서 요구하는 것들을 모두 신경써서 처리해야 한다. (구현하다 정신 나가는 줄 알았다. 특히 폰코딩이라 더더욱..)

7. 백준 16906번 - 욱제어

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

16906번: 욱제어

두 번째 난관. 트라이인 걸 몰랐다면, 트라이를 떠올리기 굉장히 어려웠을 것 같은 문제. (알고 푸는 입장에서도 '이게 왜 트라이 ?' 하는 생각이 들었다.)

어느 한 단어가 다른 단어의 접두사인지를 판별해야 하므로, 길이가 작은 순서대로 우선 정렬한다. 문자열을 구성할 때 다음과 같은 순서를 따른다.

1. 0을 현재 문자열의 끝에 붙여본다.
2. 사용할 수 있다면 계속 진행, 만약 아니라면, 즉 chk 배열값이 true라면 0을 빼고 1을 붙여본다.
3. 1을 사용할 수 있다면 계속 진행, 만약 아니라면 이전 단계의 문자열로 돌아감.
4. 위 방법으로 문자열을 만들 수 없을 경우 -1을 출력하고 프로그램 종료

위 과정은 백트래킹으로 구현하는 것이 편리하다.출력은 정렬된 순서가 아닌, 원래의 순서대로 해야 함에 주의한다.