(백준 14725 개미굴

• tags : (algorithm

  No matching post could be found

  - (trie
• 문제 링크 : https://www.acmicpc.net/problem/14725
• 풀이 링크
  • Python

• 각 점이 문자열로 이루어진 트리를 생성하고, 그 트리를 구조화하여 출력해야 한다.
• 하지만, 각 점을 이루는 문자열이 유일하지 않아 트라이 구조를 잘 만들어야 한다.

trie = defaultdict(set)
for _ in range(N):
    ants = input().strip().split()
    m = int(ants[0])
    parent = f"{ants[1]}"
    trie[""].add(parent)
    for i in range(m - 1):
        x, y = ants[1 + i], ants[2 + i]
        trie[parent].add(y)
        parent += f" {y}"

• 트라이 구조를 defaultdict으로 설정했다.
  • 각 문자열이 있는지 확인하는 조건문 등을 구현하는게 간단하지는 않을 것이라 생각했다.
  • 트라이 구조를 이루기 위해 부모로부터 각 노드를 연결하여 부모-자식 관계를 설정했다.

def search(depth: int, parent: str) -> str:
    global trie
    if not trie[parent]:
        return ""
    ans = ""
    for x in sorted(trie[parent]):
        ans += f"{'-' * (2 * depth)}{x}\n"
        child = f"{x}" if not parent else f"{parent} {x}"
        ans += f"{search(depth + 1, child)}"
    return ans

• 탐색은 for문 또는 while문으로도 가능하지만, 백트레킹으로 했다.
  • key를 기반으로 자식을 오름차순 정렬하여 탐색했다.
  • 함수의 파라미터로 깊이를 가져감으로써, 출력 구조세어 대쉬의 수를 정하였다.