[C++] 개미굴

백준 14725번

삼성 프로를 따기 위해 다시 알고리즘을 열심히 해야겠다

아직 수업을 안들어서 뭘 할까 하다가 백준 알고리즘 분류에서 내가 좋아하는 트라이를 골라서 풀어봤다

 

이 문제는 개미들이 타고 내려간 정보를 보고 개미굴의 전체 모습을 파악하는 문제

전형적인 트라이라기 보다는 트라이를 알면 쉽게 풀 수 있는 문제였던 것 같다

 

map과 vector를 사용하면서 프로 시험에 이제 stl 허용인것이 행복했다

노드별로 string을 키로 갖고 노드 포인터를 value로 갖는 map을 만들어주었다

 

로봇개미가 찾은 경로는 insert 함수를 재귀적으로 불러 차례차례 넣어주었다

이때 이미 한 번 이상 찾은 경로는 map에서 찾아서, 처음 가는 경로는 새로운 노드를 만들어 재귀함수를 불렀다

 

출력 또한 재귀적으로 함수를 호출하였는데 count라는 변수로 깊이를 파악하였다

map을 써서 또 편했던 점은 같은 층에 여러개의 방이 있을 때 사전 순으로 하라했는데 c++ map은 자동으로 사전순 정렬이므로 iterator로 반복만 시켜줘도 됐다!!

 

문제를 풀면서 print와 insert 함수를 멤버함수로 선언해야할지 전역으로 선언해서 Node*를 인자로 넣어줘야할지가 고민이었다

멤버함수로 선언했더니 this->m.find(vec[idx])->second->insert(vec,idx+1)과 같은 가독성 떨어지는 코드가 나왔다

나는 한자리에서 금방 푸니까 그냥 대충 풀고 넘기면 되는데 나중에 다시 보거나 다른 사람들에게 설명할 때는 어떤 코드가 좋을지 궁금하다

Node에서 사용하는 함수니까 멤버함수로 써야할거같기도 하고,,

아직 배울게 참 많다

 

#include <iostream>
#include <map>
#include <vector>
 
using namespace std;
 
class Node{
    public:
        map<string, Node*> m;
        void insert(vector<string> vec, int idx){
            if(idx==vec.size()){
                return;
            }
            else{
                if(this->m.find(vec[idx])==this->m.end()){
                    // create new Node
                    Node* node = new Node;
                    this->m[vec[idx]] = node;
                }
                this->m.find(vec[idx])->second->insert(vec,idx+1);
            }
        }
        void print(int count){
            for(auto it = this->m.begin() ; it != this->m.end() ; it++){
                for(int i = 0; i < count*2 ; i++) cout << "-";
                cout << it->first << "\n";
                it->second->print(count+1);
            }
        }
};
 
int main(){
    int N;
    cin >> N;
    Node* root = new Node;
 
    for(int i = 0 ; i < N ; i++){
        int K;
        cin >> K;
        vector<string> vec;
        for(int j = 0 ;j < K ; j++){
            string str;
            cin >> str;
            vec.push_back(str);
        }
        root->insert(vec,0);
    }
    root->print(0);
}