14725 개미굴

14725. 개미굴 / c++ / Gold3 / 15분

문제

https://www.acmicpc.net/problem/14725

1. 개미가 이동한 경로 N개가 주어진다.
2. 각 경로는 K개의 방을 지났다
3. 개미가 개미굴의 모든 경로를 지났을 때, 개미굴의 구조를 출력하라 (같은 레벨일 경우 사전순)

접근 방식

자료구조, 트라이

1. Node 구조체를 만든다. (깊이를 나타내는 degree와 다음 방의 음식과 포인터를 가리키는 nextFood)
2. Node* head를 만들고, N개의 경로를 head부터 파고 들어간다.
3. 각 Node의 nextFood는 map으로 만들었으므로, 선형순회하면 사전순으로 출력하게 된다.
4. degree를 이용하여 빈 문자열 prefix에 .append(degree * 2, ‘-‘) 함수를 사용해서 깊이를 표현

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <string>
#include <map>
using namespace std;

struct Node
{
    int degree;
    map<string, Node*> nextFood;

    Node(int _degree) : degree(_degree) {}
    ~Node()
    {
        for (pair<string, Node*> iter : nextFood)
        {
            delete iter.second;
        }
    }
};

int N, K;
string food;
Node* head;

void Print(string name, Node* node, int degree)
{
    string prefix = "";
    prefix.append(degree * 2, '-');
    cout << prefix << name << '\n';

    for (pair<string, Node*> iter : node->nextFood)
    {
        Print(iter.first, iter.second, node->degree);
    }
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N;

    head = new Node(0);

    while (N-- > 0)
    {
        cin >> K;

        Node* now = head;

        while (K-- > 0)
        {
            cin >> food;
            if (now->nextFood.find(food) == now->nextFood.end())
            {
                now->nextFood[food] = new Node(now->degree + 1);
            }
            now = now->nextFood[food];
        }
    }

    for (pair<string, Node*> iter : head->nextFood)
    {
        Print(iter.first, iter.second, head->degree);
    }


    return 0;
}

다시 생각해 볼 점

1. Trie 라는 개념을 알고 접근하니 훨씬 풀이가 쉬웠다.
2. Trie 는 문자 하나만 저장하는게 아닌 문자열도 사용할 수 있다.
3. Trie 를 사용할 때 Node는 보통, 다음 노드로 가는 포인터 배열과, 현재 노드에서 저장해야할 data 를 갖는다.