문제

https://www.acmicpc.net/problem/9019

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net




내 코드

http://boj.kr/836ca88b72f345bc8aa165383d3fca6b

Baekjoon Online JudgeBaekjoon Online Judgeboj.kr


25번째줄 while문에서 갑자기 안드로메다로 가버리는데 도저히 원인을 모르겟음


내 생각은

하나의 부모당 4개의 자식노드와 비슷한 구조로 bfs를 굴리면서 각 케이스마다 부모를 계속 타고올라가서 부모가 root일때(tmp->parent == NULL)

해당 케이스에서 명령문의 전체를 파악하고

그 명령문을 돌려봐서 입력값이랑 원하는값이 같을때 탈출하고

맞으면 그 명령문을 출력하려했음


근데 지금 그냥 25번째줄에서 돌다가 이상한 주소값으로 점핑해버리는데 대체 왜 그렇지? 파악을 못하겠음




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

int goal, input;
char command[4] = "DSLR";

typedef struct data{
    char cmd;
    struct data *parent;
}data;

data queue[1000]; int front, rear;

data *tmp;

char cal[5000]; int len, res;

int DSLR() {
    tmp = &queue[rear-1];
    printf("%c : ", tmp->cmd); fflush(stdout);

    len = 0;

    //cmd 기록
    while(tmp->cmd != '\0') {
        cal[len++] = tmp->cmd;
        tmp = tmp->parent;
    }
    cal[len++] = tmp->cmd;

    //cmd 실행
    res = input;
    int k = len;
    while(k--) {
        switch(cal[k]) {
            case 'D':
                res = res<<1%10000;
                break;
            case 'S':
                res = res-1 > 0 ? res-1 : 9999;
                break;
            case 'L':
                res = res/1000 + res%1000*10;
                break;
            case 'R':
                res = res%10*1000 + res/10;
                break;
            default:
                break;
        }
    }
   
    while(len--) printf("%c", cal[len]);
    printf("\n");
    fflush(stdout);
    return res;
}

void clear() {
    free(tmp);
}

void bfs() {
    front = rear = 0;
    queue[rear].cmd = '\0';
    queue[rear++].parent = NULL;
    for(int i=0; i<4; i++) {
        queue[rear].cmd = command[i]; //DSLR
        queue[rear++].parent = &queue[front];
        if(DSLR() == goal) return;
    }
    front++;
    int prear;
    while(front < rear) {
        prear = rear;
        while(front < prear) {
            for(int i=0; i<4; i++) {
                queue[rear].cmd = command[i]; //DSLR
                queue[rear++].parent = &queue[front];
                if(DSLR() == goal) return;
            }
            front++;
        }
    }
}

int main(){
    tmp = (data *)malloc(sizeof(data));
    int tc; scanf("%d", &tc);
    while(tc--) {
        scanf(" %d %d", &input, &goal);
        bfs();
        while(len--) printf("%c", cal[len]);
        printf("\n");
    }
    clear();
    return 0;
}