글 읽기 - 메모리 초과 관련 질문 드립니다

lsy980124 7년 전 0

DFS방식 사용 하였습니다.
동적할당 해제도 다하였는데 메모리 초과가 뜨네요
메모리 초과 해결할 수 있는 방법이나 조언 부탁드려도 될련지요 ㅠ

#include<stdio.h>
#include<stdlib.h>
int T;//실행회수
int N, E;//동굴의 개수  통로의 개수
int n = 1;//visit 배열 채우기 위함
int recent_profit, max_profit;//현재 이득과 이때까지 지나온 최대 이득을 비교한다
int m = 1;//n의 값을 저장하기위함(가장 큰경우의 visit도 저장해야함)
void allzero_1(int *visit)
{
	for (int i = 0; i < E; i++)
		visit[i] = 0;
}
void allzero_2(int **passage)
{
	for (int i = 0; i < N + 1; i++)
	{
		for (int j = 0; j < N + 1; j++)
			passage[i][j] = 0;
	}
}
void allzero_3(int ***loss)
{
	for (int i = 0; i < N + 1; i++)
	{
		for (int j = 0; j < N + 1; j++)
		{
			for (int k = 0; k < 1; k++)
				loss[i][j][k] = 0;
		}
	}
}
void best_profit_search(int *profit, int **passage, int ***loss, int start, int *visit, int *best_visit)
{
	int i, j, k;
	visit[n++] = start;
	if (recent_profit >= max_profit)
	{
		max_profit = recent_profit;
		for (int g = 0; g < E; g++)
			best_visit[g] = visit[g];
		m = n;
	}
	for (i = 1; i <= N; i++)
	{
		if (passage[start][i] == 1)
		{
			passage[start][i] = 0;//지나갔다는 것을 표시
			recent_profit = recent_profit - loss[start][i][0] + profit[i];
			best_profit_search(profit, passage, loss, i, visit, best_visit);
			n = n - 1;
			passage[start][i] = 1;
		}
	}
}
int main()
{
	scanf("%d", &T);
	for (int p = 0; p < T; p++)
	{
		int a, b, c;//a,b통로  c는 소모비용
		scanf("%d %d", &N, &E);
		int*profit = (int*)malloc(sizeof(int)*(N + 1));//각 동굴 이득
		int**passage = (int**)malloc(sizeof(int*)*(N + 1));
		for (int g = 0; g < N + 1; g++)
			*(passage + g) = (int*)malloc(sizeof(int)*(N + 1));
		allzero_2(passage);
		//passage(2차원 배열)동적할당 완료-통로 연결됨 표시
		int***loss = (int***)malloc(sizeof(int**)*(N + 1));
		for (int i = 0; i < N + 1; i++)
		{
			*(loss + i) = (int**)malloc(sizeof(int*)*(N + 1));
			for (int j = 0; j < N + 1; j++)
				*(*(loss + i) + j) = (int*)malloc(sizeof(int) * 1);
		}
		allzero_3(loss);
		//loss(3차원 배열)동적할당 완료-통로 이동할때마다의 손실 표시
		for (int g = 1; g <= N; g++)
			scanf("%d", &profit[g]);
		recent_profit = profit[1]; max_profit = profit[1];
		for (int g = 0; g < E; g++)
		{
			scanf("%d %d %d", &a, &b, &c);
			passage[a][b] = 1;
			loss[a][b][0] = c;
		}//그래프 그리기
		int*visit = (int*)malloc(sizeof(int)*(E + 1));
		allzero_1(visit);
		visit[0] = 1;
		int*best_visit = (int*)malloc(sizeof(int)*(E + 1));
		allzero_1(best_visit);
		best_visit[0] = 1;
		for (int start = 1; start <= N; start++)
		{
			if (passage[1][start] == 1)
			{
				passage[1][start] = 0;
				recent_profit = recent_profit - loss[1][start][0] + profit[start];
				if (recent_profit > max_profit)
					max_profit = recent_profit;
				best_profit_search(profit, passage, loss, start, visit, best_visit);//
				passage[1][start] = 1; recent_profit = profit[1]; n = n - 1;
			}
		}
		printf("%d %d\n", max_profit, m);
		for (int g = 0; g < m; g++)
			printf("%d ", best_visit[g]);
		printf("\n");
		for (int x = 0; x < N + 1; x++)
		{
			for (int y = 0; y < 1; y++)
				free(loss[x][y]);
			free(loss[x]);
		}
		free(loss);
		for (int x = 0; x < N + 1; x++)
		{
			free(passage[x]);
		}
		free(passage);
		free(visit);
		free(best_visit);
	}
}

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

문제

문제

출처

ICPC

메모리 초과 관련 질문 드립니다

lsy980124 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말