Trie

👉🏻 14725번: 개미굴문제 정의개미굴 문제는 쉽게 말해 트리의 각 계층과 구조를 얼마나 빨리 시각화할 수 있냐! 하는 문제였습니다.예를 들어 아래와 같은 트리(개미굴)의 구조가 입력되면,A--B--CB--A--C ----D위와 같이 각 가지마다 어떤 노드가 있는지를 출력하면 되는 문제입니다.(저는 우선 이 출력 구조에서 DFS를 써야겠구나를 떠올렸습니다.)Trie결정적으로 저는 이 문제에서 Trie 자료 구조를 사용하였습니다.처음에는 인접 리스트 방식으로 트리를 표현해보려다가 경로 데이터도 함께 저장해야했기 때문에 Trie를 선택하게 되었습니다.결국 문제의 핵심은 겹치는 경로는 하나로 표현해주고, 갈라지는 부분부터 가지를 쳐줘야한다는 것이었습니다.만약에 트리가 A B C / A B D로 들어오게 ..

👉🏻 14426번: 접두사 찾기import sys; input=sys.stdin.readlinefrom collections import defaultdictclass Node(object): def __init__(self): self.is_terminal = False self.children = defaultdict(Node)class Trie(object): def __init__(self): self.root = Node() def insert(self, string): node = self.root for char in string: node = node.children[char] ..