글 읽기 - 이 소스코드의 용량이 128MB를 넘길까요?

tddhot2 7년 전 0

제 생각은 항상 생각보다 128메가라는 용량이커서 남을것같은데

알고리즘 은 항상 메모리초과라고 하더군요 ㅠㅠ

#include "stdafx.h"
#include <iostream>
#include <queue>
#include <list>
#pragma warning(disable:4996)
using namespace std;

typedef struct _node {
	int weight;
	int NumBuilding;
	struct _node* link;
}Node;

int WeightArray[501] = { 0, };
queue <int>Q;


//NowNode : 현재 방문 정점 , arr : 인접 행렬 , check : 진입차수 배열 , n : 건물 개수 , max : 전파되면서 정해지는 합
void Propagation(int NowNode, Node* arr[], int n)
{
	//cout << "방문 정점 => " << NowNode << endl;
	Node* cur = arr[NowNode];

	while (cur != NULL)
	{
		//cout << "연결된 정점 " << cur->NumBuilding << "을 업데이트합니다" << endl;
		int temp = WeightArray[NowNode] + cur->weight;
		//cout << "기존 가중치 " << cur->weight << "와 이전거와 합친 가중치" << temp << "를 비교합니다" << endl;
		if (temp > cur->weight)
		{
			//cout << "새로운 가중치로 업데이트 합니다!" << endl;
			WeightArray[cur->NumBuilding] = temp;
		}
		else
		{
			WeightArray[cur->NumBuilding] = cur->weight;
		}
		Q.push(cur->NumBuilding);
		cur = cur->link;
	}

}


int main()
{
	int NumOfBuilding;
	cin >> NumOfBuilding;

	Node* BulidArray[501] = { nullptr, };

	for (int i = 1; i <= NumOfBuilding; i++)
	{
		int TimeToBuild, PriorBuilding;
		cin >> TimeToBuild;
		cin >> PriorBuilding;

		//만약 선행 건물이 없는 노드라면 시작정점(0,0)으로부터의 가중치 입력
		if (PriorBuilding == -1)
		{
			Node* newnode = (Node*)malloc(sizeof(Node));
			newnode->weight = TimeToBuild;
			newnode->NumBuilding = i;
			newnode->link = BulidArray[0];
			BulidArray[0] = newnode;
		}

		while (PriorBuilding != -1)
		{
			Node* newnode = (Node*)malloc(sizeof(Node));
			newnode->weight = TimeToBuild;
			newnode->NumBuilding = i;
			newnode->link = BulidArray[PriorBuilding];
			BulidArray[PriorBuilding] = newnode;
			cin >> PriorBuilding;
		}
	}

	Q.push(0);

	while (!Q.empty())
	{
		int Vertex = Q.front();
		Q.pop();
		Propagation(Vertex, BulidArray, NumOfBuilding);
	}

	for (int i = 1; i <= NumOfBuilding; i++)
		cout << WeightArray[i] << endl;
}

waylight3 7년 전 0

코드를 자세히 읽어보지는 않았지만, 큐에 넣어서 bfs를 도는 경우 메모리초과가 났다면 너무 많이 탐색을 돌고 있다는 뜻이 아닐까요? 보통 그런 경우 로직에 문제가 있더라구요.

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

문제

문제

출처

ICPC

이 소스코드의 용량이 128MB를 넘길까요?

tddhot2 7년 전 0

waylight3 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말