글 읽기 - 염치불구하고 1005번 질문 좀 해보겠습니다.. (런타임에러)

surung9898 5년 전 0

하루하루 전문가 니뮤들의 도움으로 살아가고 있습니다...

연결리스트를 이용하여 풀려는 시도를 하였는데 문제 예시를 포함한 1005번 관련 게시판의 모든 반례들이 제대로 돌아가는 것을 확인했씁니다...

런타임에러가 발생하는데, 유일하게 동적할당 하지 않는 q의 갯수를 100만, 300만, 700만, 1000만으로 잡았을 때 똑같이 런타임에러가 발생하여,

혹시 segmentation fault 오류로 인한 런타임 에러인지, 아니면 재귀가 너무 깊게 들어가서 그러는 것인지,

그것도 아니라면 무엇이 문제인지 한 번 혜안을 감히 요청해봅니다...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct build* next; //제 관찰력과 시야가 좁아서 택한 연결리스트
typedef struct build
{
	int gogo;
	next link;
} build;

next createN(next head, int a) //길 연결 받을때마다 연결해주는 함수
{
	next temp = NULL, c = head, trail = NULL;

	temp = (next)malloc(sizeof(build));
	temp->link = NULL;
	temp->gogo = a;

	if (!head)
	{
		head = temp;
		return head;
	}

	while (c)
	{
		trail = c;
		c = c->link;
	}

	trail->link = temp;

	return head;
}

int *time, *visit, *initial, ftcnt = 0, *finaltrail, front = -1, rear = -1;
next *b; //time = a -> b일때 b의 time에 a의 time을 추가
//visit = 방문여부
//ftcnt = 목표와 연결되어있는 건물의 갯수. 마지막에 가장 많은 time을 가진 애를 출력하기 위해 설정
//finaltrail = 목표와 연결되어있는 건물을 큐처럼 보관하는 배열
//front, rear = 큐를 쓰기위해 설정
//b = 연결리스트를 사용하는 길 연결 배열

void qq(next head, int st, int* q, int goal) //가장 문제의 함수... 제가 빡대가리입니다 미안합니다!!!!!!!
{
	next c = head, temp = NULL;

	while (c) //head가 있는데
	{
		if (c->gogo != goal) //head와 연결되있는 놈이 있는데 걔가 목표는 아니여
		{
			if (!visit[c->gogo])
			{
				rear++; //전형적인 큐
				q[rear] = c->gogo; //전형적이어버린 큐
				visit[q[rear]] = 1; //'visit' 해버렸다!
			
				if (time[c->gogo] < initial[c->gogo] + time[st]) time[c->gogo] += time[st]; //타임 추가
			}
			else if (time[c->gogo] < initial[c->gogo] + time[st])
			{
				time[c->gogo] = time[st] + initial[c->gogo]; //타임 교체
				rear++; //전형적인 큐
				q[rear] = c->gogo; //전형적이어버린 큐
				visit[q[rear]] = 1; //'visit' 해버렸다!
			}
		}
		else //걔가 목표여
		{
			finaltrail[ftcnt] = st; //목표와 연결되어있는 큐에 저☆장
			ftcnt++;
		}

		c = c->link; //네 다음
	}

	while(front < rear) //큐 아직 안끝남?
	{
		front++;
		
		qq(b[q[front]], q[front], q, goal); //ㅇㅋ recursion
	}
}

void main()
{
	int i, j, cnt, bcnt, tcnt, tmp1, tmp2, q[100055], max = 0;

	scanf("%d", &cnt);

	for (i = 0; i < cnt; i++)
	{
		scanf("%d %d", &bcnt, &tcnt); //bcnt = vertex개수 tcnt = node개수

		visit = (int*)calloc((bcnt+1), sizeof(int));
		time = (int*)calloc((bcnt+1), sizeof(int));
		initial = (int*)calloc((bcnt + 1), sizeof(int));
		b = (next*)malloc((bcnt+1) * sizeof(next));
		finaltrail = (int*)malloc(sizeof(int) * bcnt);

		for (j = 1; j <= bcnt; j++) //초기 조건 오지게 하겠습니다 행님들
		{
			scanf("%d", &tmp2);
			time[j] = tmp2;
			initial[j] = tmp2;
			b[j] = NULL;
		}

		for (j = 0; j < tcnt; j++) //연결 오지게 하겠습니다 행님들
		{
			scanf("%d %d", &tmp1, &tmp2);

			b[tmp1] = createN(b[tmp1], tmp2);
		}

		scanf("%d", &tmp1);

		for (j = 1; j <= bcnt; j++) //모든 vertex에게 평등한 기회를 주겠습니다
		{
			if (!visit[j]) //방문 안했어? 그렇다면
			{
				//visit[j] = 1;
				qq(b[j], j, q, tmp1); //qq함수를 한번 들어가 보아라
			}
		}

		j = 0;

		while (j < ftcnt) //finaltrail에 들어있는 vertex 중 가장 시간이 많이 걸리는 vertex를 엄격히 선별
		{
			if (time[finaltrail[j]] > max) max = time[finaltrail[j]];

			j++;
		}

		printf("%d\n", max + time[tmp1]); // + 목표 건물 설치 시간

		free(visit); //초기화
		free(time);
		free(b);
		free(finaltrail);
		free(initial);
		max = 0;
		front = -1;
		rear = -1;
		ftcnt = 0;
	}
	
	system("pause");
}

sinse100 5년 전 1

그 연결 구조 말고 그래프를 사용하시는건 어떤지요

surung9898 5년 전 0

@sinse100

예.. 위상정렬 이용해서 그래프로 풀면 된다는건 알고있는데, 이걸로 살릴 방법이 있는지 찾아보고싶어서... 빡대가리라 제송합니다 으흑ㅎ그휴ㅠㅠ

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

문제

문제

출처

ICPC

염치불구하고 1005번 질문 좀 해보겠습니다.. (런타임에러)

surung9898 5년 전 0

sinse100 5년 전 1

surung9898 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말