[알고리즘] 6 - PrintTree 문제에 대한 나의 해결책(DFS)

#include <iostream>
#include <vector>
#include <string>
#include <utility>      // std::pair, std::make_pair
#include <unordered_map>

using namespace std;

void DFS(int depth, string key, unordered_map<string, vector<string>> mp){
    if(!mp.count(key))// if key does not exist
        return;
    vector<string> values = mp[key];

    for (int i = 0; i < values.size(); i++){
        for (int j = 0; j < depth; j++)
            cout << "\t";
        cout << values[i] << endl;
        DFS(depth+1, values[i], mp);
    }
}

int main()
{
    vector<pair<string, string>> input;
    input.push_back(make_pair("animal", "mammal"));
    input.push_back(make_pair("animal", "bird"));
    input.push_back(make_pair("lifeform", "animal"));
    input.push_back(make_pair("cat", "lion"));
    input.push_back(make_pair("mammal", "cat"));
    input.push_back(make_pair("animal", "fish"));
    unordered_map<string, vector<string>> mp;
    unordered_map<string, bool> seen;

    for (auto p : input){

        string key = p.first;
        string val = p.second;
        seen[val] = true;


        if(mp.count(key)){
            mp[key].push_back(val);
        } else {
            vector<string> arr = {val};
            mp[key] = arr;
        }
    }

    // Finding the start point (root node)
    // 1. Brute force: Use DFS and count the height
    // 2. If the string ever appeared in the p.second (as a val) then remove from the candidate
    string root = "";
    for (auto m : mp){
        if(!seen.count(m.first)){
            root = m.first;
        }
    }
    cout << root << endl;
    DFS(1, root, mp);

    // Use DFS to print out every child
    // Need to add depth for every vector array

    return 0;
}