[Baekjoon Online Judge] 백준 14725번 개미굴(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 14725번 개미굴

(Python)

(글쓴날 : 2020.07.10)

 

---

* Baekjoon Online Judge, 백준 14725번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 14725번 개미굴

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/14725

14725번: 개미굴

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

개미굴의 층마다 들어있는 먹이 이름이 주어질 때, 문제에서 주어지는 기준에 맞추어 개미굴의 구조를 출력하는 문제입니다.

 

저의 경우, 트라이를 적용하였으며, Python을 사용했습니다.

우선, 트라이 자료구조 클래스를 만든 뒤, 문자열들을 저장하는 기능의 insert() 메소드와 구조를 출력하는 기능의 printStructure() 메소드를 구현하여 문제를 해결했습니다.

트라이 노드의 key로 먹이를 뜻하는 단어 그자체를 사용하였고 자식 노드를 연결하는 포인터의 역할로 딕셔너리를 사용했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
class Node():
 
    def __init__(self, key):
        self.key = key
        self.children = dict()
 
 
class Trie():
 
    def __init__(self):
        self.head = Node(None)
    
    def insert(self, string):
        curr_node = self.head
 
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
 
    def printStructure(self, L, curr_node):
        if L == 0:
            curr_node = self.head
        
        for child in sorted(curr_node.children.keys()):
            print("--" * L, child, sep="")
            self.printStructure(L + 1, curr_node.children[child])
 
        
trie = Trie()
 
N = int(input())
 
for _ in range(N):
    temp = list(input().split())
    trie.insert(temp[1:])
 
trie.printStructure(0, None)

---