백준 9019 / DSLR

현재까지 수행했던 경로를 string으로 담거나 역추적을 하면 된다.

string도 vector처럼 push_back과 pop_back이 가능하니 string으로 푸는 것이 편하다.

역추적하는 방법을 알아봐야겠다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<string>
using namespace std;
 
typedef struct DATA {
 
    int x;
    string path;
    int from;
    int cnt;
 
}DATA;
 
queue<DATA>q;
int a, b;
bool check[10001];
 
int main() {
 
    int testcase;
    cin >> testcase;
 
 
    while (testcase--) {
 
        memset(check, false, sizeof(check));
        cin >> a >> b;
        DATA d;
        d.x = a;
        d.cnt = 0;
        d.path = "";
        q.push(d);
 
 
        while (!q.empty()) {
            int now = q.front().x;
            int cn = q.front().cnt;
            int fm = q.front().from;
            string pt = q.front().path;
 
            if (now == b) {
 
                cout << pt << endl;;
 
                while (!q.empty()) {
                    q.pop();
                }
 
                break;
            }
            q.pop();
 
 
 
            int d1, d2, d3, d4;
 
            d1 = now / 1000;
            d2 = (now - d1 * 1000) / 100;
            d3 = (now - d1 * 1000 - d2 * 100) / 10;
            d4 = (now - d1 * 1000 - d2 * 100 - d3 * 10);
 
            DATA data;
 
            for (int i = 0; i < 4; i++) {
                //D
                if (i == 0) {
 
                    int nx = (now * 2) % 10000;
 
                    if (check[nx] == false) {
                        check[nx] = true;
                        data.x = nx;
                        pt.push_back('D');
                        data.path = pt;
 
                        data.from = now;
 
                        data.cnt = cn + 1;
 
                        q.push(data);
                        pt.pop_back();
                    }
                }
                //S
                if (i == 1) {
 
                    int nx;
                    if (now > 0) {
                        nx = now - 1;
                    }
                    if (now == 0) {
                        nx = 9999;
                    }
                    if (check[nx] == false) {
                        check[nx] = true;
                        data.x = nx;
                        pt.push_back('S');
                        data.path = pt;
                        data.from = now;
                        data.cnt = cn + 1;
 
 
                        q.push(data);
                        pt.pop_back();
                    }
 
                }
 
                //L
                if (i == 2) {
 
                    int nx;
                    nx = d2 * 1000 + d3 * 100 + d4 * 10 + d1;
                    if (check[nx] == false) {
                        check[nx] = true;
                        data.x = nx;
 
                        pt.push_back('L');
                        data.path = pt;
                        data.from = now;
 
                        data.cnt = cn + 1;
 
                        q.push(data);
                        pt.pop_back();
                    }
                }
                //R
                if (i == 3) {
 
                    int nx;
                    nx = d4 * 1000 + d1 * 100 + d2 * 10 + d3;
                    if (check[nx] == false) {
                        check[nx] = true;
                        data.x = nx;
 
                        pt.push_back('R');
                        data.path = pt;
                        data.from = now;
                        data.cnt = cn + 1;
                        q.push(data);
                        pt.pop_back();
                    }
                }
            }
 
 
 
        }
 
    }
 
}