문제

[백준] 휴대폰 자판 (Platinum 4)

요약

사전 내에 가능한 다음 글자가 하나 뿐이라면, 그 글자는 자동으로 입력된다고 하자. 각 단어를 입력하기 위해 몇 번 버튼을 눌러야 하는지 구하라.

분류

  • 트라이
  • DFS

풀이

내 풀이

트리를 생성하고 DFS로 탐색해주었다. 언제 ‘자동으로 입력될 것인지’ 결정하는 것이 관건이었다.

import sys
from collections import deque
input = sys.stdin.readline


class TrieNode:
    def __init__(self):
        self.is_end = False
        self.child_cnt = 0
        self.children = [None for _ in range(26)]


while True:
    try:
        n = int(input())
        root = TrieNode()

        for _ in range(n):
            t = root
            word = input().rstrip()
            for char in word:
                idx = ord(char) - ord('a')
                if t.children[idx] is None:
                    t.children[idx] = TrieNode()
                    t.child_cnt += 1

                t = t.children[idx]
            t.is_end = True

        stack = deque([(root, 0)])
        acc = 0
        while stack:
            cur_node, cur_cnt = stack.pop()

            if cur_node.is_end:
                acc += cur_cnt

            for child in cur_node.children:
                if child is None:
                    continue

                if cur_node.child_cnt == 1 and not cur_node.is_end and cur_cnt != 0:
                    stack.append((child, cur_cnt))
                else:
                    stack.append((child, cur_cnt + 1))

        print("%.2f" % (acc / n))

    except:
        break