2-S

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <cstring>

int N, M;
int cache[10001] = {-1,};

int traverse(std::map<int, std::vector<int>>& treeMap, int node)
{
	if (treeMap.find(node) == treeMap.end())
	{
		cache[node] = 1;
		return 1;
	}

	if (cache[node] != -1)
	{
		return cache[node];
	}

	int sum = 0;

	std::vector<int> v = treeMap[node];
	
	for (int i = 0; i < v.size(); ++i)
	{
		int tmp = traverse(treeMap, v[i]);
		sum += tmp;
	}

	cache[node] = sum + 1;

	return sum + 1;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::cin >> N >> M;
	memset(cache, -1, sizeof(cache));
	std::map<int, std::vector<int>> treeMap;
	
	for (int i = 0; i < M; ++i)
	{
		int from, to;

		std::cin >> to >> from;

		if (treeMap.find(from) == treeMap.end())
		{
			std::vector<int> v;
			v.reserve(N);
			v.push_back(to);
			treeMap[from] = v;
			continue;
		}
		
		treeMap[from].push_back(to);
	}


	std::map<int, std::vector<int>> countMap;
	int maxCount = 0;

	for (auto iter : treeMap)
	{
		const int startNode = iter.first;
		memset(cache, -1, sizeof(cache));
		int nodeCount = traverse(treeMap, startNode);
			maxCount = std::max(maxCount, nodeCount);

		if (countMap.find(nodeCount) == countMap.end())
		{
			std::vector<int> v;
			v.push_back(startNode);
			countMap[nodeCount] = v;
			continue;
		}

		countMap[nodeCount].push_back(startNode);
	}

	for (int i = 0; i < countMap[maxCount].size(); ++i)
	{
		std::cout << countMap[maxCount][i] << " ";
	}
	std::cout << std::endl;


	return 0;
}

답이 틀렸다고 나오는데 어디서 왜 틀렸는지 잘 모르겠습니다. 혹시 이 부분을 설명해주실 수 있으실까요?

int traverse(std::map<int, std::vector<int>>& treeMap, int node)
{
	//O(N)의 시간복잡도가 발생 
	if (treeMap.find(node) == treeMap.end())
	{
		cache[node] = 1;
		return 1;
	}

		std::cin >> to >> from;
		if (treeMap.find(from) == treeMap.end())
		{
			std::vector<int> v;
			//불필요한 코드 
			//v.reserve(N);

	//sort를 해주셔야 합니다.  map은 key를 기반으로 key가 정렬됩니다. 
	sort(countMap[maxCount].begin(), countMap[maxCount].end());
	
	for (int i = 0; i < countMap[maxCount].size(); ++i)
	{
		std::cout << countMap[maxCount][i] << " ";
	} 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <cstring>

int N, M;
using namespace std;  
int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr); 
	std::map<int, std::vector<int>> treeMap;
	vector<int> v1 {2, 1, 3}; 
	treeMap[1] = v1; 
	for(int it : treeMap[1]) cout << it << ' ';
	// 2 1 3 
	return 0;
}