[BOJ/Gold 3] 백준 14725 개미굴(C++)

문제 링크

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

14725번: 개미굴

 

 

문제

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

입력

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다. 

출력

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

예제 입력 1

3
2 B A
4 A B C D
2 A C

예제 출력 1

A
--B
----C
------D
--C
B
--A

예제 입력 2

4
2 KIWI BANANA
2 KIWI APPLE
2 APPLE APPLE
3 APPLE BANANA KIWI

예제 출력 2

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

알고리즘 분류

• 트라이

풀이

입력받는 N개의 데이터는 트라이를 구성하는 브랜치의 하나라고 생각하자.

예를 들면 APPLE BANANA KIWI라고 하면 Root 노드의 자식 중 하나가 APPLE이 되는 것이고, 그 APPLE의 자식 중 하나가 BANANA가 되고, 그 BANANA의 자식 중 하나가 KIWI가 되는 것이다.

모든 먹이는 최대 15자의 문자로 구성된 문자열이므로 key값을 문자열로, value값을 트라이의 포인터로 갖는 map을 자식 노드로써 구현한다.

unordered_map을 활용한다면 insert 과정에서 시간을 단축할 수 있겠지만 사전 순으로 트라이의 구조를 출력해야 하기 때문에 어차피 정렬을 한 번 해줘야 한다. 따라서 원소를 insert할 때마다 key값을 기준으로 모든 원소의 정렬이 이루어지는 map을 활용한다.

N개의 데이터를 입력받아 트라이를 완성시켰다면 DFS를 통해서 첫 번째 브랜치부터 트라이를 이루는 모든 먹이 원소를 출력하고, 이 때 깊이를 나타내는 매개변수 Depth를 추가하여 깊이를 기록해주고 깊이가 1 증가할 때마다 --를 먼저 출력시켜준다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#define INF 1e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE{
    bool isEnd;
    map<string, TRIE*> Child;
    map<string, TRIE*>::iterator IT;

    TRIE() : isEnd(false) {}
    ~TRIE() {
        for (IT = Child.begin(); IT != Child.end(); IT++) {
            delete IT->second;
        }
    }

    void insert_Food(vector<string> Vec) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Vec.size(); i++) {
            string Now = Vec[i];
            if (!NowTrie->Child[Now]) {
                NowTrie->Child[Now] = new TRIE;
            }
            NowTrie = NowTrie->Child[Now];
        }
        NowTrie->isEnd = true;
    }
};

int N, K;
string S;
vector<string> Food;

void DFS(TRIE* Trie, int Depth) {
    map<string, TRIE*>::iterator IT;
    for (IT = Trie->Child.begin(); IT != Trie->Child.end(); IT++) {
        for (int i = 0; i < Depth; i++) {
            cout << "--";
        }
        cout << IT->first << "\n";
        DFS(IT->second, Depth + 1);
    }
}

void find_Answer(TRIE* Root) {
    DFS(Root, 0);
}

void input() {
    TRIE* Root = new TRIE();
    cin >> N;
    while (N--) {
        Food.clear();
        cin >> K;
        while (K--) {
            cin >> S;
            Food.push_back(S);
        };
        Root->insert_Food(Food);
    };
    find_Answer(Root);
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}