글 읽기 - c++ 트리의 높이와 너비 메모리 초과

krocd 2년 전 0

중위순위 탐색이후 각 깊이별로 최대점 과 최소점의 차를 이용하여 너비를 구했습니다

무슨짓을 해도 57 퍼에서 메모리 초과가 뜨는데 다른 분들 코드를 참조해도 같은 방식인 배열로 많이 구현했는데 어디서 메모리가 초과가 나는지 모르겠습니다. ㅜㅜ

고수님들 도와 주십쇼 ㅜㅜ

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

using namespace std;

typedef struct _node{
	int right;
	int left;
	int depth;
	int wide_dot;
}node;

node adj_list[30001];
int input_times[30001];
int depth_arr[30001];
int r_wide_dot_arr[30001];
int l_wide_dot_arr[30001];
int order;
int node_input_times;


void inorder(int node)
{
	if(node == -1)
	{
		return;
	}

	adj_list[adj_list[node].left].depth = adj_list[node].depth + 1;
	inorder(adj_list[node].left);
	// cout << node << ":";
	order++;
	adj_list[node].wide_dot = order;
	// cout << adj_list[node].wide_dot << " ";
	adj_list[adj_list[node].right].depth = adj_list[node].depth + 1;
	inorder(adj_list[node].right);
}

void find_max()
{
	int max_depth = 0;

	for(int i = 1; i <= node_input_times; i++)
	{
		int depth = adj_list[i].depth;
		int order = adj_list[i].wide_dot;
		if(l_wide_dot_arr[depth] == 0)
		{
			l_wide_dot_arr[depth] = order;
		}
		else
		{
			l_wide_dot_arr[depth] = min(l_wide_dot_arr[depth], order);
		}
		r_wide_dot_arr[depth] = max(r_wide_dot_arr[depth], order);
		max_depth = max(max_depth, depth);
	}

	int ans = 0;
	int ans_lev = 0;
	for(int i =1; i <=max_depth; i++)
	{
		if(ans < r_wide_dot_arr[i] - l_wide_dot_arr[i] + 1)
		{
			ans = r_wide_dot_arr[i] - l_wide_dot_arr[i] + 1;
			ans_lev = i;
		}
	}
	cout << ans_lev  << " "  << ans<< "\n";
}

int main()
{

	int root = 0;
	cin >> node_input_times;

	for(int i = 0; i < node_input_times; i++)
	{
		int r, l, root;
		cin >> root >> l >> r;
		adj_list[root].left = l;
		adj_list[root].right = r;
		if(r != -1)input_times[r]++;
		if(l != -1)input_times[l]++;
	}
	for(int i = 1; i < node_input_times; i++) //루트를찾는 방법 한번만 등장하면 루트다
	{
		if(input_times[i] == 0)
		{
			root = i;
		}
	}
	adj_list[root].depth = 1;
	inorder(root); // root is not must 1!!!
	find_max();
}

krocd 2년 전 0

88번쨰줄

for(int i = 1; i <= node_input_times; i++) {

if(input_times[i] == 0)

{

root = i;

}

루트 찾는데 범위가 잘못되어 있었습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 트리의 높이와 너비 메모리 초과

krocd 2년 전 0

krocd 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말