백준/14725번/개미굴/골드3

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

문제 설명

Site: Baekjoon
Number: 14725
Category: Tree
Rank: Gold 3

모든 리프노드까지의 경로가 주어질 때, 그 경로들을 사전순으로 레벨이 내려갈때 마다 –를 추가하여 출력하는 문제입니다.

문제 풀이

모든 경로를 입력받으며 이미 존재하는 노드라면 추가하지 않고 존재하지 않는 노드라면 트리에 추가한 후, 사전순으로 정렬하여 출력하면 되는 간단한 문제입니다.

Node 구조체 하나를 만들고 이름과 Node*타입을 저장하는 벡터를 멤버 변수로 생성한 후, 노드를 입력받으며 자식 노드에 동일한 이름이 있다면 추가하지 않고 없다면 추가합니다.

트리를 완성하면 root에서 시작하며 자식들을 사전순으로 정렬 후 재귀 함수를 통해 접근하면 문제를 해결할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node
{
    Node(string name)
	    : name(name)
    {
        children.clear();
    }

    void AddChild(Node* node)
    {
        children.push_back(node);
    }

    string name;
    vector<Node*> children;
};

Node* CheckChildren(const Node* root, const string InName)
{
	for(Node* node : root->children)
	{
        if (node->name == InName)
            return node;
	}

    return nullptr;
}

void Print(Node* node, int level)
{
    sort(node->children.begin(), node->children.end(), [](Node* a, Node* b)
    {
    	return a->name < b->name;
    });

    for(Node* nd : node->children)
    {
	    for(int i = 0; i < level; i++)
	    {
            cout << "--";
	    }
        cout << nd->name << '\n';
        Print(nd, level + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N;
    cin >> N;

    Node* root = new Node("Root");

    for(int i = 0; i < N; i++)
    {
        int num;
        cin >> num;

        Node* current = root;
        for(int j = 0; j < num; j++)
        {
            string name;
            cin >> name;

            Node* node = CheckChildren(current, name);
            if (node == nullptr)
            {
                node = new Node(name);
                current->AddChild(node);
            }
            current = node;
        }
    }

    Print(root, 0);

    return 0;
}