[백준 5670] 휴대폰 자판

 

 트라이 문제. 트라이에 대해 몰라도 자료 구조와 그래프에 대해 잘 이해하고 있다면, 충분히 떠올릴 수 있다. 주어진 단어들을 가지고 트리를 만든다고 생각하면 된다. 각 문자열의 위치 별 문자가 하나의 노드가 되고, 연속된 같은 문자라면 노드를 공유하면 된다. 위의 예시를 구현하면 아래와 같은 형태가 된다.

 위 문제에서는 똑같은 단어가 두 번 주어지지 않으므로, 나는 해당 문자를 끝으로 하는 완전한 단어가 있음을 표시할 빈 노드를 만들어 사용했다(코드에서는 공백 값을 주었다). 

 

 위처럼 트라이를 구현하고 나면 어느 부분까지 자동 완성이 가능한지 쉽게 찾아낼 수 있고, 나는 DFS를 통해 각각의 완전한 단어들을 만드는 데 필요한 입력 횟수 합을 재귀적으로 받아오도록 했다.

 주의할 점은 첫 문자는 무조건 입력한 후에 모듈이 동작한다는 점이고, 그에 맞게 예외처리를 해 줄 필요가 있다. 또 메모리가 그렇게 넉넉하지 않기 때문에 C/C++로 구현한다면 메모리 관리에 주의해야 한다.