[백준/C++] 14725. 개미굴

문제

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

14725번: 개미굴

풀이

tree를 이용하여 풀이했다.

value와 자식들의 배열을 가지는 Node를 만들었고, 이 Node들을 트리로 연결한 후에 DFS로 탐색했다. 

각 Node의 자식들이 오름차순으로 정렬될 필요가 있었다. 따라서 vector대신에 map을 사용했다. map은 기본적으로 key값을 기준으로 오름차순으로 정렬되어 있기 때문이다.  

 

들어온 먹이 정보를 벡터에 저장하고, root부터 시작해서 해당하는 Node가 없으면 만들어주고, 있으면 넘어가는 식으로 삽입해주었다. 

 

후에 탐색할때는 DFS를 이용하였고, 깊이*2만큼 -를 출력한 후에 value를 출력했다. 

코드

#include <iostream>
#include <string>
#include <map>
#include <vector>

#define endl "\n";
using namespace std;

struct Node {
	string value;
	map<string, Node> child; // map : key값을 기준으로 오름차순 정렬되어 있음 
};
Node root{ "" };

void DFS(Node parent, int depth) {
	for (auto c : parent.child) { // map에서 원소 하나씩 꺼내서 반복
		string d;
		for (int i = 0; i < depth; i++) // 깊이 만큼 -- 출력
			d += "--";
		cout << d << c.second.value << endl;
		DFS(c.second, depth + 1);
	}
}

void insert(vector<string> route) {
	Node* parent = &root;
	for (int i = 0;i < route.size();i++) {
		if (parent->child.count(route[i]) == 0) {
			Node temp{ route[i] };
			parent->child[route[i]] = temp;
		}
		parent = &(parent->child[route[i]]);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int N,K; cin >> N;
	string temp;
	for (int n = 0;n < N;n++) {
		cin >> K;
		vector<string> route;
		for (int k = 0;k < K;k++) {
			cin >> temp;
			route.push_back(temp);
		}
		insert(route);
	}
	DFS(root, 0);
	return 0;
}

결과