글 읽기 - 1753번 메모리초과 오류입니다.

soulsystem00 3년 전 0

언어는 C++입니다.

원래는 파이썬으로 작성했었는데

파이썬에서 메모리 초과가 나서

C++로 작성을 해봤습니다만

똑같이 메모리초과가 일어나네요

어디를 고쳐야 할지 알려주시면 감사하겠습니다.

#include <iostream>
#define INF 1000000000
using namespace std;

int Minindex(int* arr, int* chk, int size)
{
	int min = 999999;
	int minindex = 0;
	for (int i = 0; i < size; i++)
	{
		if (min > arr[i] && chk[i] == 0)
		{
			min = arr[i];
			minindex = i;
		}
	}
	chk[minindex] = 1;
	return minindex;
}

int* Dijkstra(int** arr, int node, int start)
{
	int* tmp = new int[node];
	int* chk = new int[node];
	for (int i = 0; i < node; i++)
	{
		tmp[i] = arr[start][i];
		chk[i] = 0;
	}

	int minindex = Minindex(tmp, chk, node);
	int addnum = tmp[minindex];

	for (int k = 0; k < node; k++)
	{
		for (int j = 0; j < node; j++)
		{
			int tmpnum = addnum + arr[minindex][j];
			if (tmpnum < tmp[j])
			{
				tmp[j] = tmpnum;
			}
		}
		minindex = Minindex(tmp, chk, node);
		addnum = tmp[minindex];
	}
	delete[] chk;
	return tmp;
}

void input(int& node, int& line, int& start)
{
	cin >> node >> line;

	cin >> start;
}

int** initArray(int node)
{
	int** arr = new int* [node];
	for (int i = 0; i < node; i++)
	{
		arr[i] = new int[node];
	}
	for (int i = 0; i < node; i++)
	{
		for (int j = 0; j < node; j++)
		{
			arr[i][j] = INF;
		}
	}
	return arr;
}

void inputArray(int** arr, int line)
{
	for (int i = 0; i < line; i++)
	{
		int x, y, num;
		cin >> x >> y >> num;
		arr[x - 1][y - 1] = num;
	}
}

void printresult(int* tmp, int start, int node)
{
	tmp[start - 1] = 0;
	for (int i = 0; i < node; i++)
	{
		if (tmp[i] == INF)
			cout << "INF" << '\n';
		else
			cout << tmp[i] << '\n';
	}
}
int main()
{
	int node;
	int line;
	int start;
	input(node, line, start);

	int** arr = initArray(node);
	inputArray(arr, line);


	int* tmp = Dijkstra(arr, node, start - 1);
	printresult(tmp, start, node);
	delete[] arr;
	delete[] tmp;
}

djm03178 3년 전 0

인접 행렬로 만들게 되면 O(V^2)의 메모리가 필요하기 때문에 너무 큽니다. 인접 리스트를 사용해서 O(V+E) 메모리에 구현해 보세요.

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

문제

문제

출처

ICPC

1753번 메모리초과 오류입니다.

soulsystem00 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말