글 읽기 - 메모리 초과 발생 이유

1212combat 6년 전 0

메모리 초과가 발생하는데 이유를 모르겠네요.

​

#include <stdio.h>
#include <malloc.h>

#define TRUE        1
#define FALSE        0

//typedef int(*Arr)[3];

/* 12라인 부터 77 라인은 Queue 자료구조 표현 
   Queue에 넣을 때는 value(3x3 을 int값으로 표현)와 bfs 정점 이동 거리를 cost에 저장 
*/
typedef struct _data{
    int value;
    int cost;
}Data;

typedef struct _node
{
    Data data;
    struct _node *next;
}Node;

typedef struct _queue
{
    Node *front;
    Node *rear;
}Queue;

void QInit(Queue *pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}

int QIsEmpty(Queue *pq)
{
    if (pq->front == NULL)
        return TRUE;
    else
        return FALSE;
}

void Enqueue(Queue *pq, Data data)
{
    Node *nd = (Node*)malloc(sizeof(Node));
    nd->data.value = data.value;
    nd->data.cost = data.cost;
    nd->next = NULL;
    if (QIsEmpty(pq))
    {
        pq->front = nd;
        pq->rear = nd;
    }
    else
    {
        pq->rear->next = nd;
        pq->rear = nd;
    }
}

Data Dequeue(Queue *pq)
{
    Node *rpos = pq->front;
    Data rdata;
    rdata.value = rpos->data.value;
    rdata.cost = rpos->data.cost;
    pq->front = rpos->next;
    free(rpos);
    return rdata;
}

Data QPeek(Queue *pq)
{
    return pq->front->data;
}

/* 기준이 되는 값 */
int order = 123456780

Queue q;

int bfs(Data input)
{
    Data here, there;
    char i, idx;
    int temp1, temp2, temp3;    

    /* 최초 입력값이 기준이되는 123456780 과 같으면 종료 */
    if (input.value == order)
        return input.cost;

    /* Q를 초기화 하고, 최초 입력값을 Enqueue 에 넣음 */
    QInit(&q);
    Enqueue(&q, input);

    /* 다른 bfs 알고리즘처럼 Queue 가 빌 때까지 무한 반복 */
    while (!QIsEmpty(&q))
    {
        /* dequeue 해서 Queue에서 값을 빼냄 */
        here = Dequeue(&q);        
        
        /* here.value 에서 0이 위치되는 자리수를 idx 변수에 저장 */
        temp2 = here.value;
        for (idx = 0; idx < 9; idx++)
        {
            temp1 = temp2 % 10;
            temp2 = temp2 / 10;
            if (temp1 == 0)
            {
                break;
            }
        }
        
        /* temp3 에 현재 0이 되는 자리수 만큼 10을 거듭제곱해 줌*/
        temp3 = 1;
        for (i = 0; i<idx; i++)
            temp3 = temp3 * 10;
        
        /* 빈칸을 왼쪽 값과 교환하려고 함.
        하지만, 빈칸이 맨 왼쪽에 있는 경우, 왼쪽에 있는 값과 교환할 수 없음.
        idx 가 2, 3, 8 의 경우 맨 왼쪽에 있기에 맨 왼쪽에 빈칸이 존재하지 않을 경우 */
        if ((idx != 2 && idx !=3) && idx != 8)
        {
            temp1 = temp3 * 10;
            temp2 = (here.value / temp1)%10;
            there.value = here.value - temp2*temp1 + temp2*temp3;
            there.cost = here.cost + 1;
            if (there.value == order)
                return there.cost;
            Enqueue(&q, there);
        }

        /* 빈칸을 오른쪽 값과 교환하려고 함.
        하지만, 빈칸이 맨 오른쪽에 있는 경우, 오른쪽에 있는 값과 교환할 수 없음.
        idx 가 0, 5, 6 의 경우 맨 오른쪽에 있기에 맨 오른쪽에 빈칸이 존재하지 않을 경우 */
        if ((idx != 0 && idx != 5) && idx != 6)
        {
            temp1 = temp3 / 10;
            temp2 = (here.value / temp1) % 10;
            there.value = here.value - temp2*temp1 + temp2*temp3;
            there.cost = here.cost + 1;
            if (there.value == order)
                return there.cost;
            Enqueue(&q, there);
        }

        /* 빈칸을 위쪽 값과 교환하려고 함.
        하지만, 빈칸이 맨 위쪽에 있는 경우, 위쪽에 있는 값과 교환할 수 없음.
        idx 가 6이상이면 맨 위쪽에 빈칸이 있기에, 맨 위쪽에 빈칸이 존재하지 않을 경우 */
        if (idx < 6)
        {
            temp1 = temp3 * 1000;
            temp2 = (here.value / temp1) % 10;
            there.value = here.value - temp2*temp1 + temp2*temp3;
            there.cost = here.cost + 1;
            if (there.value == order)
                return there.cost;
            Enqueue(&q, there);
        }
        /* 빈칸을 아래쪽 값과 교환하려고 함.
        하지만, 빈칸이 맨 아래쪽에 있는 경우, 아래쪽에 있는 값과 교환할 수 없음.
        idx 가 2이하이면 맨 아래쪽에 빈칸이 있기에, 맨 아래쪽에 빈칸이 존재하지 않을 경우 */
        if (idx > 2 )
        {
            temp1 = temp3 / 1000;
            temp2 = (here.value / temp1) % 10;
            there.value = here.value - temp2*temp1 + temp2*temp3;
            there.cost = here.cost + 1;
            if (there.value == order)
                return there.cost;
            Enqueue(&q, there);
        }
    }

    return -1;
}

int main()
{
    Data input;
    int i, ret, temp;
    input.value = 0;
    for (i = 0; i < 9; i++)
    {
        scanf_s("%d", &temp);
        input.value = input.value * 10 + temp;
    }
    input.cost = 0;
    ret = bfs(input);
    printf("%d\n", ret);
    return 0;
}

djm03178 6년 전 1

171줄이나 되는 코드를 질문을 올리면서 코드에 대한 설명 한 줄 없다니, 솔직히 너무하다고 생각합니다.

이래서는 코드에 대한 직접적인 답변은 못 드리고, 생각해볼 거리만 제시해드릴 수 있습니다.

1. 메모리 제한이 16MB인 건 염두에 두셨나요?

2. 큐에 들어갈 수 있는 경우의 수가 얼마나 되는지 고려해보셨나요?

3. 중복 방문은 안 일어나는 게 확실한가요?

1212combat 6년 전 0

djm03178 님 말씀이 맞네요. 주석 추가하였습니다.

말씀하신 관점에서 좀 더 고민해 보도록 하겠습니다.

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

문제

문제

출처

ICPC

메모리 초과 발생 이유

1212combat 6년 전 0

djm03178 6년 전 1

1212combat 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말