[BOJ/백준][Gold2] 14725 : 개미굴 (C++)

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

14725번: 개미굴

 

[난이도] Gold2
[유형] Trie

[풀이]
Trie 문제인데 정렬을 이용하여 간단히 풀 수 있습니다.
출력을 할 때, 먹이정보가 오름차순으로 빠른 순서인 개미의 정보부터 출력을 해야합니다.
예를 들어, A B C E 보다 A B C D 인 먹이정보를 가져온 개미의 정보부터 출력을 해야합니다.
각 개미의 먹이정보를 vector<string>에 넣은 뒤 정렬하면 vector의 comparator에 의해 저절로 오름차순으로
정렬이 되기 때문에
정렬 된 이후 0~N-1 번 개미의 먹이정보를 순차적으로 출력해주면 됩니다.

i-1번 개미 : A B C D
  i번 개미 : A B C E

먹이정보가 위와 같은 경우에는
i번 개미의 정보를 찍을 때, A,B,C는 이미 i-1번 개미의 정보를 찍을 때 찍은 E의 조상 노드이므로
출력을 하면 안됩니다.
이를 확인하기 위해 단순하게 i번 개미의 먹이정보를 출력하기 전에 i-1번 개미의 먹이정보가 비교해서
i-1,i가 같은 먹이 (위의 예시에서 A,B,C) 까지는 출력을 하지 않으면 됩니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N,K;
vector<string> v[1000]; 
string line(int k){
    string ret;
    while(k--) ret+="--";
    return ret;
}
int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        vector<string> t;
        cin >> K;
        while(K--){
            string s;
            cin >> s;
            t.push_back(s);
        }
        v[i]=t;
    }
    sort(v,v+N);
    for(int i=0;i<N;i++){
        int d=0;
        if(i!=0){
            for(int j=0;j<v[i].size()&&j<v[i-1].size();j++){
                if(v[i][j]==v[i-1][j]) d++;
                else break;
            }
        }
        for(int j=d;j<v[i].size();j++) cout << line(j)+v[i][j] << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/14725.cpp