[백준] 14725 개미굴 with C++

문제설명

---

입출력 예제

---

개념

　부모 노드를 기준으로 트리가 어떻게 구성되어 있는지 파악하는 문제다. 문자열을 효율적으로 관리하는 트라이(trie) 자료 구조를 활용하거나, 트리를 구성해 DFS 탐색을 이용해 문제를 풀어도 되지만, 필자는 set의 자동 정렬 특성을 이용해 모든 문자열 경로를 알파벳 순서로 정렬하고, 이에 해당하는 구조를 출력하는 방식으로 문제를 해결하였다.

---

풀이(1)

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
	int N, n;
	cin >> N;
	set<string> s;

	while (N--)
	{
		string tmp, str;
		cin >> n;
		
		while (n--)
		{
			cin >> tmp;
			str += ' ' + tmp;
			s.insert(str);
		}
	}

　먹이 정보의 개수 N을 입력받은 후, 문자열을 자료형으로 갖는 집합 s를 초기화한다. 그리고 입력받은 문자열을 순차적으로 붙여나간다. 이렇게 하면 각 문자열이 포함되는 모든 경로가 s에 들어가게 된다. 예를 들어 "4 A B C D"가 입력되었다면, "A" "A B" "A B C" "A B C D"가 모두 s에 저장된다. 이는 알파벳 순으로 자동 정렬하는 set의 특징에서 기인한다.

 

	for (const auto& str : s)
	{
		int cnt = count(str.begin(), str.end(), ' ');
		int index = str.find_last_of(' ');
		string ans = str.substr(index + 1);

		for (int i = 0; i < 2 * (cnt - 1); ++i)
			cout << '-';
		cout << ans << "\n";
	}
}

　이제 집합에 저장된 모든 경로를 출력한다. 이때 출력 형식은 공백의 개수에 따라 '-'이 들여 쓰기 역할을 한다. 이때 공백의 개수는 현재 경로의 깊이를 의미하므로, 각 노드의 깊이를 출력에 반영할 수 있다. 그리고 find_last_of() 함수를 사용하여 마지막 노드의 이름을 찾아 출력한다. 이렇게 하면 모든 경로를 깊이에 따라 알파벳 순으로 출력할 수 있다.

 

총합본

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
	int N, n;
	cin >> N;
	set<string> s;

	while (N--)
	{
		string tmp, str;
		cin >> n;
		
		while (n--)
		{
			cin >> tmp;
			str += ' ' + tmp;
			s.insert(str);
		}
	}

	for (const auto& str : s)
	{
		int cnt = count(str.begin(), str.end(), ' ');
		int index = str.find_last_of(' ');
		string ans = str.substr(index + 1);

		for (int i = 0; i < 2 * (cnt - 1); ++i)
			cout << '-';
		cout << ans << "\n";
	}
}

---

풀이(2) DFS 활용

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct Node
{
    map<string, Node*> children;
};

void DFS(Node* node, int level)
{
    for (auto child : node->children) 
    {
        for (int i = 0; i < level; ++i) 
            cout << "--";
        
        cout << child.first << '\n';
        DFS(child.second, level + 1);
    }
}

int main() 
{
    int N;
    cin >> N;
    Node* root = new Node();

    while (N--)
    {
        int K;
        cin >> K;
        vector<string> arr(K);

        for (int j = 0; j < K; j++) 
            cin >> arr[j];

        Node* temp = root;

        for (const auto& str : arr) 
        {
            if (temp->children.count(str) == 0) 
                temp->children[str] = new Node();
            
            temp = temp->children[str];
        }
    }

    DFS(root, 0);
}