글 읽기 - Segfault 원인을 알고 싶습니다.

adfsfsf 3년 전 0

구체적으로는, 처음에 Segfault로 떴다가 시간이 지난 후에 OutOfBounds로 바뀝니다. 어떤 배열의 크기가 문제인지 모르겠습니다.
#include <stdio.h>

#define MAXLENGTH 200001

//끝점과 해당 점까지의 현재 거리를 저장하는 힙이다.
//거리가 짧은 것이 앞으로 나온다.
int minLengthVoltex[200005][2];

//간선 배열이다. 출발점이 작은 수인 것이 가장 앞으로, 끝 점이 작은 것이 앞으로, 길이가 짧을 수록 앞으로 나오게 정렬할 것이다.
int Lines[300001][3];

//정렬을 위한 임시배열이다.
int tmp[300001][3];

//각 정점 별로, 해당 정점이 시작점인 선의 시작 인덱스를 저장하고 있다. 값이 0이라면 시작점이 없는 것이다.
int startLines[20001] = { 0 };

int Lengths[20001];

//힙의 index 값에 새로운 값을 집어넣는다.
void putToHeap(int length, int voltex, int index);

int popFromHeap(int index);

void mergeSort(int p, int r);

void merge(int left, int mid, int right);

int main(void) {

	//힙에서 새로운 값이 들어갈 위치의 인덱스
	int indexOfHeap = 1;

	int V, E;
	int K;
	int i;
	int checkStartPoint, checkFinishPoint;//출발점이 K인 선이 처음 나오는 지점 및 K+1인 선이 나오는 지점
	int checkLength;

	scanf("%d %d", &V, &E);

	scanf("%d", &K);

	for (i = 0; i < E; i++)
	{
		scanf("%d %d %d", &Lines[i][0], &Lines[i][1], &Lines[i][2]);
		checkLength = Lines[i][0];
		startLines[checkLength]++;
	}

	for (i = 1; i <= V; i++)
	{
		startLines[i] = startLines[i - 1] + startLines[i];
		Lengths[i] = MAXLENGTH;
	}

	mergeSort(0, E - 1);

	Lengths[K] = 0;

	while (K != 0)
	{
		if (K == 1) checkStartPoint = 0;
		else checkStartPoint = startLines[K - 1];
		checkFinishPoint = startLines[K];

		for (i = checkStartPoint; i < checkFinishPoint; i++)
		{
			checkLength = Lines[i][2] + Lengths[K];
			if (Lengths[Lines[i][1]] > checkLength)
			{
				putToHeap(checkLength, Lines[i][1], indexOfHeap);
				indexOfHeap++;
			}
		}

		K = 0;

		if (indexOfHeap > 1)
			K = minLengthVoltex[1][1];

		if (K != 0)
		{
			Lengths[minLengthVoltex[1][1]] = minLengthVoltex[1][0];
			indexOfHeap = popFromHeap(indexOfHeap - 1) + 1;
		}
	}

	for (i = 0; i < V; i++)
	{
		if (Lengths[i + 1] == MAXLENGTH)
			printf("INF\n");
		else
			printf("%d\n", Lengths[i + 1]);
	}

	return 0;

}

void putToHeap(int length, int voltex, int index)
{
	int indexOfNew = index;
	int indexForCheck = index / 2;
	if (index == 1)
	{
		minLengthVoltex[index][0] = length;
		minLengthVoltex[index][1] = voltex;
		return;
	}
	while (indexForCheck > 0)
	{
		if (minLengthVoltex[indexForCheck][0] > length)
		{
			minLengthVoltex[indexOfNew][0] = minLengthVoltex[indexForCheck][0];
			minLengthVoltex[indexOfNew][1] = minLengthVoltex[indexForCheck][1];
		}
		else
			break;
		indexOfNew = indexForCheck;
		indexForCheck = indexForCheck / 2;
	}
	minLengthVoltex[indexOfNew][0] = length;
	minLengthVoltex[indexOfNew][1] = voltex;
}

int popFromHeap(int index)
{
	int indexOfMax = index;//현재 힙에서 마지막 값의 위치
	int indexForCheck;//pop과정에서, 직전에 가장 마지막에 있던 노드의 위치를 조정하기 위한 변수
	int lengthForCheck, voltexForCheck;
	int checkLeftChild, checkRightChild;//조정용 변수 기준, 자식 노드들의 인덱스
	int checkNum;//조정될 인덱스 저장
	while (Lengths[minLengthVoltex[1][1]] <= minLengthVoltex[1][0])
	{

		lengthForCheck = minLengthVoltex[indexOfMax][0];
		voltexForCheck = minLengthVoltex[indexOfMax][1];
		indexForCheck = 1;
		indexOfMax--;
		if (indexOfMax == 0)
			break;
		if (indexOfMax > 1)
		{
			while (1)
			{
				checkNum = -1;
				checkLeftChild = indexForCheck * 2;
				checkRightChild = checkLeftChild + 1;
				if (checkLeftChild <= indexOfMax)
				{
					checkNum = checkLeftChild;
					if (checkRightChild <= indexOfMax)
						if (minLengthVoltex[checkRightChild][0] < minLengthVoltex[checkLeftChild][0])
							checkNum = checkRightChild;
				}
				if (checkNum == -1)
					break;

				if (minLengthVoltex[checkNum][0] > lengthForCheck)
				{
					minLengthVoltex[indexForCheck][0] = lengthForCheck;
					minLengthVoltex[indexForCheck][1] = voltexForCheck;
					break;
				}
				else
				{
					minLengthVoltex[indexForCheck][0] = minLengthVoltex[checkNum][0];
					minLengthVoltex[indexForCheck][1] = minLengthVoltex[checkNum][1];
				}

				indexForCheck = checkNum;
			}
		}

		minLengthVoltex[indexForCheck][0] = lengthForCheck;
		minLengthVoltex[indexForCheck][1] = voltexForCheck;
	}

	return indexOfMax;
}

void mergeSort(int p, int r) {
	int sortCheck[300001][5];
	int ind, mid, maxind;
	ind = 0;
	sortCheck[ind][0] = p;
	sortCheck[ind][1] = r;
	sortCheck[ind][2] = -1;
	maxind = 0;
	while (ind >= 0)
	{
		if (sortCheck[ind][3] == -1)
		{
			if (sortCheck[ind][4] == -1)
			{
				mid = (sortCheck[ind][0] + sortCheck[ind][1]) / 2;
				merge(sortCheck[ind][0], mid, sortCheck[ind][1]);
                if(sortCheck[ind][2]!=-1)
                {
                    if (sortCheck[sortCheck[ind][2]][3] == ind)
					    sortCheck[sortCheck[ind][2]][3] = -1;
				    else
					    sortCheck[sortCheck[ind][2]][4] = -1;
                }
				ind = sortCheck[ind][2];
			}
			else
			{
				ind = sortCheck[ind][4];
				continue;
			}
		}
		else if (sortCheck[ind][0] < sortCheck[ind][1])
		{
			mid = (sortCheck[ind][0] + sortCheck[ind][1]) / 2;
			sortCheck[maxind + 1][2] = ind;
			sortCheck[maxind + 1][1] = mid;
			sortCheck[ind][3] = maxind + 1;
			sortCheck[maxind + 1][0] = sortCheck[ind][0];
			maxind++;
			sortCheck[maxind + 1][2] = ind;
			sortCheck[maxind + 1][1] = sortCheck[ind][1];
			sortCheck[ind][4] = maxind + 1;
			sortCheck[maxind + 1][0] = mid + 1;
			maxind++;
			ind = sortCheck[ind][3];
		}
		else
		{
			if (sortCheck[sortCheck[ind][2]][3] == ind)
				sortCheck[sortCheck[ind][2]][3] = -1;
			else
				sortCheck[sortCheck[ind][2]][4] = -1;
			ind = sortCheck[ind][2];
		}
	}
}

void merge(int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;
	while (i <= mid && j <= right) {
		if (Lines[i][0] < Lines[j][0])
		{
			tmp[k][0] = Lines[i][0];
			tmp[k][1] = Lines[i][1];
			tmp[k][2] = Lines[i][2];
			k++;
			i++;
		}
		else if (Lines[i][0] > Lines[j][0])
		{
			tmp[k][0] = Lines[j][0];
			tmp[k][1] = Lines[j][1];
			tmp[k][2] = Lines[j][2];
			k++;
			j++;
		}
		else if (Lines[i][1] < Lines[j][1])
		{
			tmp[k][0] = Lines[i][0];
			tmp[k][1] = Lines[i][1];
			tmp[k][2] = Lines[i][2];
			k++;
			i++;
		}
		else if (Lines[i][1] > Lines[j][1])
		{
			tmp[k][0] = Lines[j][0];
			tmp[k][1] = Lines[j][1];
			tmp[k][2] = Lines[j][2];
			k++;
			j++;
		}
		else if (Lines[i][2] <= Lines[j][2])
		{
			tmp[k][0] = Lines[i][0];
			tmp[k][1] = Lines[i][1];
			tmp[k][2] = Lines[i][2];
			k++;
			i++;
		}
		else
		{
			tmp[k][0] = Lines[j][0];
			tmp[k][1] = Lines[j][1];
			tmp[k][2] = Lines[j][2];
			k++;
			j++;
		}
	}
	if (i > mid) {
		for (l = j; l <= right; l++)
		{
			tmp[k][0] = Lines[l][0];
			tmp[k][1] = Lines[l][1];
			tmp[k][2] = Lines[l][2];
			k++;
		}
	}
	else {
		for (l = i; l <= mid; l++)
		{
			tmp[k][0] = Lines[l][0];
			tmp[k][1] = Lines[l][1];
			tmp[k][2] = Lines[l][2];
			k++;
		}
	}
	for (l = left; l <= right; l++) {
		Lines[l][0] = tmp[l][0];
		Lines[l][1] = tmp[l][1];
		Lines[l][2] = tmp[l][2];
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

Segfault 원인을 알고 싶습니다.

adfsfsf 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
