[BOJ] 14725번 - 개미굴

백준 14725번 - 개미굴

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1843	1162	918	65.014%

문제

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

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

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

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

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

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

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

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

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

• 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

출처

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

14725번: 개미굴

알고리즘 분류

• 자료구조
• 문자열
• 트리
• 트라이

접근 방법

문제를 읽고 순서대로 따라 읽어내려가보면, 개미들이 주는 정보들이 root에서부터 leaf까지의 정보가 주어진다는 것을 알 수 있다.

만약 특정 서브트리의 root가 자식을 2개 이상 가진다면, 이 경로들은 다른 개미들이 알려주는 정보에도 포함이 되는 정보일 것이다.

Trie에 대하여 잘 모르더라도, 트리에 대한 지식만 있다면 쉽게 풀 수 있을 것이라 예상된다. 단, 중복되는 노드들을 트리에 여러번 추가한다면 출력 값이 매우 이상해 질 수 있는 것을 감안하여 푼다.

이전에, Trie라는 자료구조에 대하여 설명해 놓은 글이 있다. 잘 읽어보면 문제에서 구현해야하는 것이 Trie임을 쉽게 알 수 있을 것이다.

2021.08.10 - [자료구조 + 알고리즘/기초] - Trie(트라이) 자료구조

Trie(트라이) 자료구조

이 문제에서 주의해서 보아야 하는 것은 다음 노드를 표현하는 key이다. 단순하게 Trie에 문자열을 저장하기 위해서 각각의 노드들은 하나의 영문자를 대표하지만, 주어진 문제에서 각각의 영문자로 저장하는 방법은 트리의 높/낮이를 깨뜨릴 수 있기 때문에 각각의 영문자로 저장하는 것을 적절한 방법이 아닌 것 처럼 보인다.

 

그러면 문자열 그 자체를 Key로 보아야하는데, 이것을 map으로 관리해주었다. ( unordered_map 이라는 해쉬테이블이 있는데, 이는 순서를 보장하지 못하므로 정렬하는 과정이 추가적으로 필요하다 )

map이 표현하는 바는 k개의 문자열이 주어졌고 m번째 문자열을 trie에 추가하고자 할 때, m 이전까지 문자열을 확인했고 m번째 문자열을 추가하고자 하는데, m번째 문자열이 이전에 추가된 적이 있으면 해당 주소를 찾아주고 추가된 적이 없으면 새로 동적할당하여 map에 저장한다는 것이다.

 

모든 문자열들이 추가 된 후, trie의 루트 노드에서 부터 깊이에 맞춰 형식대로 출력해주기만 하면 된다. 이 부분은 어려운 것이 하나도 없으므로 설명을 생략하겠다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N;
struct TrieNode{
    string strData;
    map<string, TrieNode*> mp;
    TrieNode(){strData = "", mp.clear();}
};
class Trie{
public:
    TrieNode* root;
    Trie(){root = new TrieNode();}
    void insert(TrieNode* current, string data){
        TrieNode* keyNode = current->mp[data];
        if( keyNode == nullptr ){
            keyNode = new TrieNode();
            current -> mp[data] = keyNode;
        }
        keyNode -> strData = data;
    }
    void prtAllNode(TrieNode* current, int depth){
        if( current == nullptr )
            return;
        for(int i=1; i<depth; i++)
            cout << "--";
        if( current != root )
            cout << current->strData << '\n';

        for(auto item : current->mp){
            prtAllNode(item.second, depth+1);
        }
    }
};
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N;
    Trie trie;
    for(int i=0; i<N; i++){
        int k;
        cin >> k;

        TrieNode* current = trie.root;
        for(int j=0; j<k; j++){
            string in;
            cin >> in;
            trie.insert(current, in);
            current = current->mp[in];
        }
    }
    trie.prtAllNode(trie.root, 0);
    return 0;
}