[ 백준 BOJ ] 14725번 - 개미굴 (C++)

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

 

 

생각 흐름

1. 한 줄 한 줄에 대해 정렬을 하면 출력에 나와야 하는 순서대로 정렬되는 것을 확인
2. map<string, bool> m[15]을 사용하여 나왔던 문자인지 확인해준다. 예를 들어 m[1]["BANANA"]의 값을 확인해서 1 depth에 BANANA가 나왔던 적이 있는지 확인한다.
3. 만약 BANANA가 나왔었으면 무시해주고, 안 나왔으면 출력해준다.
4. 만약 어떤 depth의 첫 문자에서 다른 문자로 바꼈으면 m을 해당 depth부터 초기화 해준다. 예를 들어 첫 문자열 중 depth 1에서 첫  문자가 A인데 다음 문자열의 depth 1인 값이 B이면 m을 초기화 해줘야 한다.
5. 왜냐하면 새로운 가지가 생기는 것이므로 depth에서 중복된 것이 나올 수 있으므로 기존의 m에 저장되어있던 true를 지워줘야 한다.

더 좋은 방법이 있을 거 같아서 다른 풀이를 봤는데 구조체를 만들어서 하면 더 쉽게 풀 수 있다.

 

 

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <memory.h>
#include <set>
#include <algorithm>

#define endl '\n'

using namespace std;

int N;
vector<string> v[1000];
map<string, bool> m[15];

bool comp(vector<string> a, vector<string> b){
    long minSize = min(a.size(), b.size());
    
    for(int i = 0; i<minSize; i++){
        if(a[i]==b[i]) continue;
        
        return a[i]<b[i];
    }
    
    return a.size()<b.size();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    
    for(int i = 0; i<N; i++){
        int n;
        cin>>n;
        for(int j = 0; j<n; j++) {
            string s;
            cin>>s;
            v[i].push_back(s);
        }
    }
    
    sort(v, v+N, comp);
    
    vector<string> first(15);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<v[i].size(); j++){
            if(first[j].empty()){
                first[j] = v[i][j];
            } else {
                if(first[j]!=v[i][j]){
                    first[j]=v[i][j];
                    for(int h = j; h<15; h++){
                        m[h].clear();
                    }
                }
            }
            if(m[j][v[i][j]]){
                continue;
            }
            else {
                m[j][v[i][j]] = true;
                for(int h = 0; h<j; h++){
                    cout<<"--";
                }
                cout<<v[i][j]<<endl;
            }
        }
    }
    
    return 0;
}