🏫 개미굴 (Class 6)

👉🏻 14725번: 개미굴

---

문제 정의

• 개미굴 문제는 쉽게 말해 트리의 각 계층과 구조를 얼마나 빨리 시각화할 수 있냐! 하는 문제였습니다.
• 예를 들어 아래와 같은 트리(개미굴)의 구조가 입력되면,

A
--B
--C
B
--A
--C
----D

• 위와 같이 각 가지마다 어떤 노드가 있는지를 출력하면 되는 문제입니다.
• (저는 우선 이 출력 구조에서 DFS를 써야겠구나를 떠올렸습니다.)

---

Trie

• 결정적으로 저는 이 문제에서 Trie 자료 구조를 사용하였습니다.
• 처음에는 인접 리스트 방식으로 트리를 표현해보려다가 경로 데이터도 함께 저장해야했기 때문에 Trie를 선택하게 되었습니다.
• 결국 문제의 핵심은 겹치는 경로는 하나로 표현해주고, 갈라지는 부분부터 가지를 쳐줘야한다는 것이었습니다.
  • 만약에 트리가 A B C / A B D로 들어오게 된다면, Trie 자료구조는 A B까지의 경로는 공유해주고, C와 D에서는 갈라지도록 구현을 할 수가 있습니다. 그래서 별도로 중복 처리를 해주지 않아도 됩니닷!
  • 이런 장점 덕분에 입력이 많아도 앞부분의 경로가 같다면, 새로운 노드를 생성하지 않게 됩니다. (완전 효율적)
• 마지막에 알파벳 순으로 정렬해서 출력해야 했는데, 이것도 결국 각 노드가 자식들을 딕셔너리 형태로 가지고 있기 때문에, key 값을 정렬해주면 깔끔하게 출력할 수 있었습니다.
• 전에 Trie 자료 구조를 사용했었던 적이 있어서 그런지 무난하게 떠올릴 수 있었습니다. (접두사 관련 문제)

🥈 14426번: 접두사 찾기

---

제출 코드

'''
트리 구조가 주어지면 이를 시각화하는 문제이다.
시각화할 때는 DFS로 한 번 접근해보게따

어떤 자료구조로 접근해야할까?
- 중복이 가능해야함

보통 구축할 때, {'A':['B', 'C'], 'B': ['D', 'E']} 이런 구조로 defaultdict로 구현하는 것이 일반적인데,
이 문제는 트리가 구축될 때마다(처음 요소가 처음 나왔을 때마다) 다른 트리에 또 구축을 해줘야할 것 같은 그런 느낌.
예를 들어,

3
2 B A
4 A B C D
2 A C

입력이 들어오면, 
B가 처음 들어왔으므로 {'B': ['A']}
그 다음 줄에서 A가 처음 들어왔으므로, {'A': ['B'], 'B': ['C'], 'C': ['D']}
그 다음 줄에서는 A가 이전에 있었으므로, {'A': ['B', 'C'], 'B': ['C'], 'C': ['D']}

근데 이렇게 할 경우에도 중복이 발생하면 안 되니까...
전에 썻던 트라이 구조를 가져가면 괜찮아 보인다
'''
import sys; input=sys.stdin.readline

class Node:
    '''
    트라이의 각 노드를 나타내는 클래스
    children 딕셔너리로 자식 노드 저장해주기
    '''
    def __init__(self):
        self.children = {}

class Trie:
    '''
    개미굴 구조
    '''
    def __init__(self):
        self.root = Node()

    def insert_path(self, path):
        '''
        주어진 경로를 개미굴에 넣어주는 함수
        '''
        cur_node = self.root

        for food in path:
            if food not in cur_node.children:
                cur_node.children[food] = Node()

            cur_node = cur_node.children[food]

    def dfs_visualize(self):
        '''
        트라이를 DFS 방식으로 출력하는 함수
        '''
        def _dfs(node, depth):
            # 현재 노드의 자식들을 알파벳 순서로 정렬
            sorted_children = sorted(node.children.keys())

            for name in sorted_children:
                # 깊이에 따라서 '--' 추가
                print('--' * depth + name)
                # 자식 노드를 DFS로 탐색하는 구조
                _dfs(node.children[name], depth + 1)

        _dfs(self.root, 0)

N = int(input())
trie = Trie()

for _ in range(N):
    path_info = list(input().split())
    K, path = int(path_info[0]), path_info[1:]

    trie.insert_path(path)

trie.dfs_visualize()