백준 9019 DSLR

<링크>

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

<소스코드>

#include<stdio.h>
#include<queue>
#include<string>
#include<math.h>
#include<stack>
#include<string.h>
using namespace std;
void bfs(int, int);
void trace(pair<int,int>[], int);
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int A, B;
        scanf("%d%d", &A, &B);
        bfs(A, B);
        printf("\n");
    }
}
void bfs(int A, int B)
{
    int isVisited[10000] = { 0, };
    pair<int, int> before[10000];
    queue<int> q;
    isVisited[A] = 1;
    before[A] = { -1,-1 };
    q.push(A);
    while (!q.empty())
    {
        int n = q.front();
        q.pop();
        if (n == B) {
            trace(before, B); return;
        }
        int to[4];
        to[0] = n * 2 % 10000;
        to[1] = n == 0 ? 9999 : n - 1;
        to[2] = n % 1000 * 10 + n / 1000;
        to[3] = n % 10 * 1000 + n / 10;
        for (int i = 0; i < 4; ++i)
            if (!isVisited[to[i]])
            {
                isVisited[to[i]] = 1;
                before[to[i]] = { i,n };
                q.push(to[i]);
            }
    }
}
void trace(pair<int,int> before[],int n)
{
    stack<int> st;
    while (before[n].first!=-1)
    {
        st.push(before[n].first);
        n = before[n].second;
    }
    while (!st.empty())
    {
        switch (st.top())
        {
        case 0:printf("D"); break;
        case 1:printf("S"); break;
        case 2:printf("L"); break;
        case 3:printf("R"); break;
        }
        st.pop();
    }
}
 

<풀이>

1. 나올 수 있는 숫자는 0~9999이다.

2. bfs를 해서 A에서 B까지 몇 번만에 가냐가 중요한게 아니고 가는 경로를 기록해야한다.

처음엔 그냥 연산자만 기록하면서 가려했는데 'D' 연산 때문에 애매해질 것 같았다.

예를 들어
D연산을 통해 100이라는 숫자가 되었다면
이전 숫자는 50일 수도 있고 5050일 수도 있기 때문이다.

3. before[10000] 배열을 만들어서 내 이전의 숫자와 연산을 저장했다.

어차피 한 번 방문한 노드는 다시 보지않기 때문에 겹칠일도 없고 

before에 기록된 모든 숫자들은 다 최단거리로 온거니깐 믿고 참조하면 된다.

1234 →L 2341 →L 3412

before[1234] = {-1,-1}
before[2341] = {1234 , L}
before[3412] = {2341 , L}

4. B부터 시작해서 before[ ]를 계속 참조하며 A가 나올때까지 stack에 넣는다.

5. 싹다 pop하면 정순서가 나온다.