글 읽기 - C) 자꾸만 메모리 초과가 발생합니다...

jms020524 2년 전 0

방문 체크로 큐에 같은 값이 들어가지 못하게 한거 같은데 계속 메모리 초과가 발생해요

디버깅으로 A = 1212에서 L과 R이 같은 수를 큐에 못넣는것 까지 확인했는데 무엇이 문제인지 모르겠습니다.

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

struct Node {
	int num;
	struct Node* next;
};

struct Queue {
	struct Node *front, *rear;
	int size;
};

struct Node* newNode(int num) {
	struct Node* node = (struct Node*)malloc(sizeof(struct Node));
	
	node->num = num;
	node->next = NULL;
	return node;
}

struct Queue* createQueue() {
	struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
	
	queue->front = queue->rear = NULL;
	queue->size = 0;
	return queue;
}

void push(struct Queue* q, int n) {
	struct Node* temp = newNode(n);
	
	q->size++;
	if(q->size == 1) {
		q->front = q->rear = temp;
		return;
	}
	
	q->rear->next = temp;
	q->rear = temp;
}

int pop(struct Queue* q) {
	struct Node* temp = q->front;
	int n = q->front->num;
	
	if(q->size == 1)
		q->front = q->rear = NULL;
	else
		q->front = q->front->next;
		
	q->size--;
	free(temp);
	return n;
}

int L(int n) {
	int d1 = n/1000;
	n = n*10 + d1;
	return n%10000;
}

int R(int n) {
	int d4 = n%10;
	n = n/10 + d4*1000;
	return n;
}

void decode(int* visit, int B, int A, char* cmd) {
	int x;
	
	while(A != B) {
		x = visit[B];
		if(visit[L(B)] == x-1) {
			*cmd++ = 'R';
			B = L(B);
		}
		else if(visit[R(B)] == x-1) {
			*cmd++ = 'L';
			B = R(B);
		}
		else if(visit[(B+1)%10000] == x-1) {
			*cmd++ = 'S';
			B = (B+1)%10000;
		}
		else {
			*cmd++ = 'D';
			if(visit[B/2] == x-1)
				B = B/2;
			else
				B = (10000+B)/2;
		}
	}
	
	*cmd = '\0';
}

int len(char *str) {
	int n = 0;
	while(*str++)
		n++;
	return n;
}

void swap(char *a, char *b) {
	char temp = *a;
	*a = *b;
	*b = temp;
}

int main() {
	int T;
	scanf("%d",&T);

	while(T--) {
		int A,B;
		scanf("%d %d",&A,&B);
		
		struct Queue* q = createQueue();
		int visit[10000] = {};
		visit[A] = 1;
		push(q,A);
		
		while(q->size) {
			int n = pop(q);
			int x = visit[n];
			
			if(n == B)
				break;
			
			int j = (n*2)%10000;
			if(!visit[j]) {
				push(q,j);
				visit[j] = x+1;
			}
				
			j = (n > 0) ? n-1 : 9999;
			if(!visit[j]) {
				push(q,j);
				visit[j] = x+1;
			}
			
			j = L(n);
			if(!visit[j]) {
				push(q,j);
				visit[j] = x+1;
			}
			
			j = R(n);
			if(!visit[j]) {
				push(q,j);
				visit[j] = x+1;
			}
		}
		
		char cmd[128];
		decode(visit, B, A, cmd);
		
		int k = len(cmd);
		int i;
		for(i = 0; i < k/2; i++)
			swap(&cmd[i],&cmd[k-1-i]);
			
		printf("%s\n",cmd);
	}
}

djm03178 2년 전 1

매 케이스마다 사용했던 큐의 메모리를 해제해주어야 합니다.

이 문제는 한 파일에 테스트 케이스가 엄청나게 많기 때문에 할당받았던 메모리를 해제하지 않고 누적시키면 어마어마한 양의 메모리를 사용하게 됩니다.

jms020524 2년 전 0

printf 다음에 free(q)를 추가해서 돌려도 똑같이 메모리초과가 발생합니다.

djm03178 2년 전 1

q만 해제하면 안 되고, 그 안에 들어있는 모든 원소에 대한 메모리를 전부 해제해줘야 합니다.

jms020524 2년 전 0

해결했습니다! 감사합니다!

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

문제

문제

출처

ICPC

C) 자꾸만 메모리 초과가 발생합니다...

jms020524 2년 전 0

djm03178 2년 전 1

jms020524 2년 전 0

djm03178 2년 전 1

jms020524 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말