글 읽기 - 1260 공간 할당 후에 마지막 free() 부분에서 오류가 나는데 도와주세요..

dlaehdeod 6년 전 0

133번의 free() 부분을 다 지우면 정답이 맞다고 나오는데

제가 할당시킨 공간을 해제해주고 싶은데 런타임 오류가 나네요

무슨 문제인지 잘 모르겠네요.. 도와주세요 ㅠ_ㅠ

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

typedef struct Graph
{
	int *visited;
	int **edge;
}Graph;

typedef struct Stack
{
	int pointer;
	int *stack;
}Stack;

typedef struct Queue
{
	int front;
	int reer;
	int *queue;
}Queue;

void createGraph(Graph *g, int n)
{
	g->visited = (int*)malloc(sizeof(int) * n);       //g->visited[0]은 생략 g->visited[1]~[n]
	memset(g->visited, 0, sizeof(int) * n);
	g->edge = (int**)malloc(sizeof(int) * n);         //g->edge[1]~[n]
	memset(g->edge, 0, sizeof(int) * n);
	for (int i = 0; i < n; ++i)
	{
		g->edge[i] = (int*)malloc(sizeof(int) * n);   //g->edge[1] 의 [1]~[n], [2] 의[1]~[n]..
		memset(g->edge[i], 0, sizeof(int) * n);
	}
}

void createStack(Stack *s, int m)
{
	s->stack = (int*)malloc(sizeof(int) * m);      //간선크기만큼 스택 배열생성
	memset(s->stack, 0, sizeof(int) * m);
	s->pointer = -1;
}

void createQueue(Queue *q, int m)
{
	q->queue = (int*)malloc(sizeof(int) * m);       //간선크기만큼 큐 배열생성
	memset(q->queue, 0, sizeof(int) * m);
	q->front = -1;
	q->reer = -1;
}

int main()
{
	Graph g;
	Stack s;
	Queue q;

	int printStack[1001] = { 0 }, stackCount = -1;   //스택 순회값 저장
	int printQueue[1001] = { 0 }, queueCount = -1;   //큐 순회값 저장

	int n, m, v, from, to, startNum, i; 
	// n=정점 m=간선개수 v=시작정점 from,to 로 간선연결, startNum 순회기준 정점, for 문 i
	scanf("%d %d %d", &n, &m, &v);

	createGraph(&g, n + 1);
	createStack(&s, m + 1);
	createQueue(&q, m + 1);

	for (i = 0; i < m; ++i)
	{
		scanf("%d %d", &from, &to);   //양방향 그래프
		g.edge[from][to] = 1;
		g.edge[to][from] = 1;
	}

	q.queue[++(q.reer)] = v;     // q.queue[0] = v

	while (q.front < q.reer)
	{
		startNum = q.queue[++(q.front)];   //dequeue

		if (g.visited[startNum] == 0)
		{
			g.visited[startNum] = 1;
			printQueue[++queueCount] = startNum;   //방문한 정점을 배열에 저장

			for (i = 1; i <= n; ++i)
			{
				if (g.visited[i] == 0 && g.edge[startNum][i] > 0)
				{
					q.queue[++(q.reer)] = i;  //enqueue
				}
			}
		}
	}

	s.stack[++(s.pointer)] = v;         // s.stack[0] = v
	memset(g.visited, 0, sizeof(int) * (n + 1));     //방문 재활용 초기화

	while (s.pointer > -1)
	{
		startNum = s.stack[s.pointer--];     //pop

		if (g.visited[startNum] == 0)
		{
			g.visited[startNum] = 1;
			printStack[++stackCount] = startNum;    //방문한 정점을 배열에 저장

			for (i = n; i > 0; --i)
			{
				if (g.visited[i] == 0 && g.edge[startNum][i] > 0)
				{
					s.stack[++(s.pointer)] = i;   //push
				}
			}
		}
	}
	
	for (i = 0; i <= stackCount; ++i)
	{
		printf("%d ", printStack[i]);
	}

	printf("\n");

	for (i = 0; i <= queueCount; ++i)
	{
		printf("%d ", printQueue[i]);
	}

	printf("\n");

	free(q.queue);
	free(s.stack);
	free(g.visited);
	for (i = 0; i <= n; ++i)
	{
		free(g.edge[i]);
	}
	free(g.edge);	
	return 0;
}

djm03178 6년 전 0

할당은 0부터 n-1까지밖에 안 해줬는데 해제는 n까지 하려고 하니까 문제가 됩니다.

dlaehdeod 6년 전 0

createGraph(&g, n + 1); 를 통해

n이 7이면

g.edge[8][8] 이 되게 만들었습니다..

이상하게 free(q.queue) 쪽을 만나자마자 에러가 뜨게 되네요..

힙영역 버퍼의 끝 공간을 사용했다는 식으로요..

djm03178 6년 전 1

아... 코드를 제대로 파악하지 못하고 답변했었네요. 역시 눈으로 디버깅하면 실수가 잦네요. 다시 한 번 볼게요.

djm03178 6년 전 1

아 뭔지 나왔습니다.

28번째 줄에 보면 g->edge는 int **형이기 때문에 할당 시에 int * 형이 n개 있는 만큼의 공간이 할당되어야 하는데, 크기를 sizeof(int *)이 아니라 sizeof(int)로 줬기 때문에 크기가 모자랍니다.

환경에 따라서는 int는 4바이트고 포인터는 8바이트일 수 있고, 채점 환경도 그렇습니다. 이건 free 자체에서 문제가 생겼다기 보다는 이미 이전에 침범한 흔적을 free 함수가 발견했다고 할 수 있겠네요.

dlaehdeod 6년 전 0

악 그렇네요.. ㅠㅠ 정말 감사합니다!! 위에는 문제 없겠지 했는데 범인은 역시 제 손이군요.. 감사합니다!!

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

문제

문제

출처

ICPC

1260 공간 할당 후에 마지막 free() 부분에서 오류가 나는데 도와주세요..

dlaehdeod 6년 전 0

djm03178 6년 전 0

dlaehdeod 6년 전 0

djm03178 6년 전 1

djm03178 6년 전 1

dlaehdeod 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말