글 읽기 - 메모리 초과 (어린양을 구원해 주소서)

totoyang 6년 전 0

안녕하십니까 알고리즘 고수 형님들.

저는 최근 문제풀이에 재미가 들린 어린양입니다.

다름이 아니라 메모리 초과에 대한 질문이 생겨 이렇게 글을 쓰게 되었습니다.

최단거리 합에 대한 경로 탐색 문제라고 생각하고 풀었습니다만, 채점이 시작하고 얼마 지나지 않아 바로 메모리 초과 판정을 받았는데요.

도저히 혼자 해결이 되지 않아 이렇게 고수형님들의 도움을 받고자합니다.

부족한 저에게 도움을 주시기 바랍니다.

감사합니다.

초보 드림.

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

using namespace std;

void searchMinDistance(unsigned int &min, int distance, const vector<vector<int>> &farmRoute, const int &targetNode, int currentNode, vector<bool> visited) 
{
	// cut branch
	if (min != 0 - 1 && min < distance)
		return;
	
	// Arrive at targetNode 
	if (currentNode == targetNode) 
	{
		if (min > distance)
			min = distance;
		return;
	}
		
	// preventing infinite-loop
	// ** distance += val: In "go to next level"
	// ** visited update out of "go to next level"
	visited[currentNode] = true; 

	// go to next level
	for (unsigned int nextNode= 0; nextNode< farmRoute.size(); ++nextNode) 
	{
		if (farmRoute[currentNode][nextNode] != 0 && visited[nextNode] == false)
			searchMinDistance(min, distance + farmRoute[currentNode][nextNode], farmRoute, targetNode, nextNode, visited);
	}
	
}

int main() {
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<vector<int>> farmRoute(N, vector<int>(N, 0));
	for (int i = 0; i < N - 1; ++i) {
		int u, v, d;
		cin >> u >> v >> d;

		farmRoute[u - 1][v - 1] = d;
		farmRoute[v - 1][u - 1] = d;
	}

	vector<bool> visited(N);

	for (unsigned int targetNode = 0; targetNode < farmRoute.size(); ++targetNode)
	{
		unsigned int sumOfDistanceForEachTargetNode = 0;
		for (unsigned int startNode = 0; startNode < farmRoute.size(); ++startNode)
		{
			if (startNode != targetNode)
			{
				unsigned int minDistancePerEachNodeToTarget = 0 - 1;
				searchMinDistance(minDistancePerEachNodeToTarget, 0, farmRoute, targetNode, startNode, visited);
				sumOfDistanceForEachTargetNode += minDistancePerEachNodeToTarget;
			}
		}
		
		cout << sumOfDistanceForEachTargetNode << '\n';
	}

	return 0;
}

jh05013 6년 전 0

30만 * 30만 벡터를 잡으니까 메모리 초과입니다. 이렇게 간단하게 풀리는 문제가 아닙니다.

upple1 6년 전 1

일단 n의최댓값이 30만으로 제곱하면 900억으로 각 1바이트라할지라도 충분히 메모리초과되겠네요.

이 그래프는 트리형이기 때문에 각 노드마다 중복되는 엣지가 없는 경로가 유일한게 힌트가 될 것 같네요

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

문제

문제

출처

ICPC

메모리 초과 (어린양을 구원해 주소서)

totoyang 6년 전 0

jh05013 6년 전 0

upple1 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말