백준 14725번 개미굴[C++]

1. 개요

 안녕하세요! 오늘 문제의 유형은 트라이입니다. 트라이는 문자열의 문자를 정점으로 하는 트리 자료구조인데요. 이번 문제는 트라이 응용이 필요한 문제였습니다.

 

저는 트라이를 중첩 구조로 구현하여 문자가 아닌 문자열 값을 가지게 구현한 다음 recursion하게 호출하여 삽입과 출력을 구현했어요!

 

2. 문제 풀이

 문제에 제시된 그림을 통해 개미굴이 트리임을 알 수 있습니다. 여기서 각 트리 정점은 숫자가 아닌 문자열 정보를 가지고 있어야 해요. 그렇다면 문자열로 정점을 분류할 수 있을까요? 정답은 분류할 수 없다입니다. 그림을 확인해 보면 서로 다른 계층에 같은 문자열을 가지고 있음을 알 수 있어요. 그래서 문자열로 정점을 분류할 수 없습니다.

 

 정점을 분리하기 위해서는 다른 논리적인 방법이 필요해보입니다. 문제의 출력부에 가시면 힌트를 얻을 수 있는데요.  

최상위 굴을 포함하여 하나의 굴에서 개미굴이 여러 개로 나뉠 때 먹이 종류별로 최대 한 번만 나올 수 있다.

 이 설명으로 임의의 정점의 자손들은 중복되는 문자열 값이 없다는 것을 보장합니다.

 

 각 정점마다 필요한 정보는 무엇일까요? 정점이 가지는 문자열값과 자손을 잇는 자료구조입니다. 저는 Trie라는 객체를 선언하였고, Trie에는 string과 map<string, Trie>를 두어서 관리하게 했습니다. 이로써 각 정점마다 값을 가지고 map을 통해 자동 정렬하면서 자손을 조회할 수 있게 되었습니다. 값 삽입과 출력 구현부는 어렵지 않아 코드로 확인해 보시면 되겠습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

class Trie{
    private:
        string value;
        map<string, Trie> nodes;

        bool is_exists(string &v) {
            return nodes.find(v) != nodes.end();
        }

    public:
        Trie(): value("") {}
        Trie(string &value): value(value) {}

        void insert(vs &v, int idx) {
            if(idx == sz(v)) {
                return;
            }

            string cur = v[idx];
            
            if(!is_exists(v[idx])) {
                nodes.insert({v[idx], Trie(v[idx])}); 
            }

            nodes[v[idx]].insert(v, idx + 1);
        }

        void print(int depth) {
            for(auto cur : nodes) {
                cout << string(depth << 1, '-') << cur.X << nl;
                cur.Y.print(depth + 1);
            }
        }

};

int n, k;

int main() {
    fastio(nullptr, false);
    
    Trie root;

    cin >> n;
    while(n--) {
        cin >> k;

        vs a(k);
        for(auto &str : a) {
            cin >> str;
        }

        root.insert(a, 0);
    }

    root.print(0);
}

 

4. 제출 결과