[백준 14725] 개미굴

 

 자료 구조 문제다. 트라이를 구현해서 푸는 것이 정석 풀이인 것 같은데, 먹이 이름으로 주어지는 문자열의 길이가 15이고 N이 최대 1,000인데 굳이 도입의 필요성은 못 느꼈다.

 입력 값이 클린하게 주어지기 때문에, 트리를 구축하기 쉽다. 나는 노드 클래스를 만들고, 자식 노드들을 <string, Node*> 형태의 map(C++ STL 기준)으로 가지도록 했다. 먹이 정보의 수가 컸다면, 삽입에 O(log N)만큼 소모되는 map을 택하기 껄끄러웠겠지만 다행히 N과 K 모두 범위가 그리 크지 않다. 그래서 어차피 정렬된 형태로 결과를 출력할 필요가 있기 때문에 정렬된 상태를 보장할 수 있는 map을 선택했다.

 

 Node 클래스를 정의하고 나면 로직은 심플하다. 각 로봇 개미들이 보내준 먹이 정보를 바탕으로 트리를 구축한다. 현재 먹이 방 노드의 자식 중에 새로 입력받은 먹이 이름을 key 값으로 하는 자식이 있는지 찾는다. 그리고 자식이 있다면 그 자식을 레퍼런싱 해서 현재 먹이 방 노드를 갱신해서 다음 먹이 이름을 입력받으면 되고, 그런 이름의 자식이 없다면 현재 노드의 자식에 새롭게 추가해 주고, 새롭게 추가한 노드로 현재 노드를 갱신해 주면 된다.

 

 모든 입력에 대해 이 과정을 반복해, 하나의 트리를 구축하고 나면 루트 노드부터 DFS로 탐색하며 노드 정보를 출력해준다. 출력할 때 붙이는 대시는 DFS 함수에 파라미터로 depth를 넘겨 알맞게 출력할 수 있다. 그리고 이미 map을 사용했기 때문에 자식들이 key값을 바탕으로 정렬된 상태를 보장하고 있고, 자연스럽게 사전순으로 DFS를 진행하게 된다.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Node {
public:
    string food;
    map<string, Node*> children;

    Node(string food) {
        this->food = food;
        children = map<string, Node*>();
    }

    void traversal(int depth) {
        for(int i=0; i<depth; i++) {
            cout << "--";
        }
        cout << food << "\n";

        for(auto child: children) {
            child.second->traversal(depth+1);
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, depth;
    string food;

    cin >> n;

    Node root = Node("root");

    for(int i=0; i<n; i++) {
        cin >> depth;

        Node* curNode = &root;
        for(int k=0; k<depth; k++) {
            cin >> food;
            auto iter = curNode->children.find(food);
            if(iter==curNode->children.end()) {
                Node* newNode = new Node(food);
                curNode->children.insert({food, newNode});
                curNode = newNode;
            } else {
                curNode = iter->second;
            }
        }
    }

    for(auto child: root.children) {
        child.second->traversal(0);
    }
}