[c++] BOJ 14725 :: 개미굴

문제

개미굴 문제 바로가기

14725번: 개미굴

 

풀이

• 여러 개의 트리를 만든 다음 레벨 순회로 출력한다.

 

코드

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

using namespace std;

struct Node {
    string name;
    vector<Node*> children;
    int level;
    Node(string n, int l) {
        name = n; level = l;
    }
};

int N;
vector<Node*> burrow;

bool compare(Node* a, Node* b) {
    if (a->name < b->name) {
        return true;
    }else{
        return false;
    }
}

void dfs(Node*& root) {
    for (int i = 0; i < root->level; i++) {
        cout << "--";
    }
    cout << root->name << '\n';

    if (root->children.size() == 0) return;

    sort(root->children.begin(), root->children.end(), compare);
    for (int i = 0; i < root->children.size(); i++) {
        dfs(root->children[i]);
    }
}

Node* getCorrectNode(vector<Node*>& arr, Node*& target) {
    for (int i = 0; i < arr.size(); i++) {
        if ((arr[i]->name == target->name) && (arr[i]->level == target->level))
            return arr[i];
    }
    arr.push_back(target); // 새로운 노드 등장
    return target;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        string s; cin >> s;
        Node* newRoot = new Node(s, 0);
        newRoot = getCorrectNode(burrow, newRoot);

        for (int j = 1; j < num; j++) {
            cin >> s;
            auto newNode = new Node(s, j);
            newNode = getCorrectNode(newRoot->children, newNode);
            newRoot = newNode;
        }
    }

    sort(burrow.begin(), burrow.end(), compare);
    for (int i = 0; i < burrow.size(); i++) {
        dfs(burrow[i]);
    }
}

 

결과

아이디	메모리	시간	코드 길이
gmldms784	2424	4	1377