/<> 백준 9019번 : DSLR (C언어)

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

 

 

BFS와 큐를 이용해 문제를 빠르게 해결할 수 있겠다는 생각에 싱글벙글 코드를 써가기 시작했지만... 기존 BFS 문제와 다른 몇 가지 특징이 C언어를 쓰는 저에게 귀찮음을 선사해주었습니다.

 

1. 테스트 케이스가 존재

 

2. 명령어 배열 따로 만들기

 

위와 같은 특징이 있기에, 함수를 따로 만들지 않고 메인 함수에 모두 작성하였습니다. 특히나 테스트 케이스 때문에 전역 변수를 선언할 수도 없었습니다. 처음에 방문 배열 visit를 전역에서 정의를 한 바람에 문제를 틀렸습니다. 이에 주의합시다.

 

또한 BFS를 통해 명령어의 순서를 찾았더라도 이를 첫 순서부터 출력해야 하기에 큐를 역추적해야 합니다. 따라서 명령어 배열 말고도 큐의 원소들의 부모 노드를 저장하는 배열을 만들었습니다. 쓰이는 배열이 많기에 함수를 만들기가 귀찮아졌습니다..(그래서 메인 함수에 작성함)

 

L, R 연산은 함수를 따로 만들었습니다. 10의 자릿수 연산을 잘 활용하면 됩니다.

 

아무튼 이 조건들을 모두 참고하여 문제를 푼다면 다른 난관은 없을 것입니다.

 

아 참고로 큐를 역추척할 때 인덱스를 불러들이는 경우, rear가 아닌 front를 이용해야 합니다.. 단순한 사실이지만 이거땜에 또 출력값이 제대로 안나왔었습니다.

 

 

<코드>

#include <stdio.h>

int shift_left(int num) {
    int first = num / 1000;
    int other = num % 1000;
    int new = (other * 10 + first) % 10000;
    return new;
}

int shift_right(int num) {
    int last = num % 10;
    int other = num / 10;
    int new = (last * 1000 + other) % 10000;
    return new;
}

int visit[10000];

int main() {
    int T;
    scanf("%d", &T);
    
    while (T--) {
        int num, result;
        scanf("%d %d", &num, &result);
        
        for(int i = 0; i < 10000; i++) visit[i] = 0;
        
        int queue[10000], command[10000], parent[10000];
        int front = 0, rear = 0;
        
        queue[rear] = num;
        command[rear] = 0;
        parent[rear++] = -1;
        visit[num] = 1;
        
        while (front < rear) {
            int curr_num = queue[front];
            int curr_command = command[front];
            int curr_parent = parent[front++];
            
            if (curr_num == result) {
                int index = front - 1;
                char command_word[10000];
                int idx = 0;
                
                while (parent[index] != -1) {
                    if (command[index] == 1) command_word[idx++] = 'D';
                    else if (command[index] == 2) command_word[idx++] = 'S';
                    else if (command[index] == 3) command_word[idx++] = 'L';
                    else if (command[index] == 4) command_word[idx++] = 'R';
                    
                    index = parent[index];
                }
                
                for (int i = idx - 1; i >= 0; i--) printf("%c", command_word[i]);
                printf("\n");
                break;
            }
            
            int new1 = (2 * curr_num) % 10000; // D 연산
            int new2 = curr_num - 1;           // S 연산
            if (new2 == -1) new2 = 9999;
            int new3 = shift_left(curr_num);   // L 연산
            int new4 = shift_right(curr_num);  // R 연산
            
            if (!visit[new1]) {
                queue[rear] = new1;
                command[rear] = 1;
                parent[rear] = front - 1;
                visit[new1] = 1;
                rear++;
            }
            if (!visit[new2]) {
                queue[rear] = new2;
                command[rear] = 2;
                parent[rear] = front - 1;
                visit[new2] = 1;
                rear++;
            }
            if (!visit[new3]) {
                queue[rear] = new3;
                command[rear] = 3;
                parent[rear] = front - 1;
                visit[new3] = 1;
                rear++;
            }
            if (!visit[new4]) {
                queue[rear] = new4;
                command[rear] = 4;
                parent[rear] = front - 1;
                visit[new4] = 1;
                rear++;
            }
        }
    }

    return 0;
}

 

 

큐에 새로운 원소를 넣는 과정이 4번 반복인지라 함수를 만드는게 코드가 훨씬 간결합니다. 하지만 함수의 인자가 많기에.. 그냥 복붙해서 썼습니다(사실 front랑 rear도 테스트 케이스 내부 변수이기에 전역 변수가 아니므로 함수 만들기가 까다로움).