반응형

 

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

 

14725번: 개미굴

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

트라이의 개념을 모른다면 공부하고 이 문제를 푸는 것을 추천합니다!

 

문제의 조건에서 사전 순으로 출력하라고 했으므로 map 자료구조를 이용해서 문제를 풀었습니다. 각각의 노드들은 자식 노드를 가지고 있고, 자식 노드들의 키값은 string입니다. 따라서 map <string, Trie*> map을 만들어 주고 이 노드는 자식 노드의 정보를 포인터의 형식으로 가지고 있습니다.

 

먹이를 벡터로 입력 받아서 만약 해당 깊이에 단어가 존재한다면 그 단어의 자식 노드로 넘어가고, 없다면 단어를 동적 할당을 통해 생성해줍니다. 그러고 나서 자식 노드로 넘어가게 됩니다.

 

이러한 방식으로 모든 입력을 처리하면 map의 특성상 자동으로 오름차순으로 정렬이 되기때문에 따로 정렬해줄 필요 없이 Find 함수를 통해서 출력해주면 됩니다.

 

Find 함수 또한 iiterator를 차례로 순회해주면서 dfs와 비슷한 방식으로 출력해주면 됩니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<string>
#include<map>
#include<vector>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie*> m;        //오름차순으로 출력하기 위해서 map을 씀
    ~Trie() {                    //소멸자로 동적 할당한 Trie들을 delete
        for (auto it = m.begin(); it != m.end(); it++) {
            delete it->second;
        }
    }
 
    void Insert(vector<string> vect, int idx)
    {
        if (vect.size() == idx) return;    //모두 삽입했다면 return
 
        if (m.find(vect[idx]) == m.end()) {    //vect[idx]가 map에 없다면
            m.insert({ vect[idx], new Trie });
        }
 
        m[vect[idx]]->Insert(vect, idx + 1);    //다음 단어를 삽입
    }
 
    void Find(int depth)
    {
        for (auto it = m.begin(); it != m.end(); it++) {
            for (int i = 0; i < depth; i++) {
                printf("--");
            }
            cout << it->first << '\n';
            
            it->second->Find(depth + 1);
        }
    }
};
 
int main()
{
    Trie *root = new Trie();
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        vector<string> vect(n);
        for (int j = 0; j < n; j++) {
            cin >> vect[j];
        }
 
        root->Insert(vect, 0);
    }
 
    root->Find(0);
    delete root;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25

+ Recent posts

티스토리툴바