728x90
SMALL

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

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번: 접두사 찾기
👉🏻 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 =
injoycode.tistory.com
제출 코드
'''
트리 구조가 주어지면 이를 시각화하는 문제이다.
시각화할 때는 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()728x90
LIST
'알고리즘 문제 풀이 > Class (solved.ac)' 카테고리의 다른 글
| 🏫 전깃줄 - 2 (Class 5++) (2) | 2025.11.04 |
|---|---|
| 🏫 낚시왕 (Class 5++) (0) | 2025.10.27 |
| 🏫 벽 부수고 이동하기 4 (Class 5++) (0) | 2025.03.04 |
| 🏫 공항 (Class 5++) (0) | 2025.02.26 |
| Class 2 (팩토리얼 0의 개수 ~ 좌표 정렬하기) (4) | 2023.12.20 |