[C++/BFS] 백준 9019 DSLR

코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
struct n {
    int number; // 숫자
    string res; // 연산과정
};
 
bool isVisit[10001];
queue<struct n> q;
 
int calD(int n){ // D연산
    return (n * 2) % 10000;
}
 
int calS(int n) { // S연산
    return n-1 >= 0 ? n-1 : 9999;
}
 
int calL(int n) { // L연산
    return (n % 1000) * 10 + n / 1000;
}
 
int calR(int n) { // R연산
    return n / 10 + (n % 10) * 1000;
}
 
void solve(int start, int end) {
    int D,S,L,R;
    q.push({ start, ""}); // 숫자, 연산과정
    isVisit[start] = true; // 방문 표시
 
    while (!q.empty()) {
        int nowNum = q.front().number; // 숫자
        string nowStr = q.front().res; // 연산 과정
        q.pop();
 
        if (nowNum == end) {
            // 연산 결과가 원하던 값일 경우 연산 과정 출력 후 종료
            cout << nowStr << endl;
            return;
        }
 
        D = calD(nowNum);
        S = calS(nowNum);
        L = calL(nowNum);
        R = calR(nowNum);
        if (!isVisit[D]) {
            isVisit[D] = true; // 방문 표시
            q.push({ D, nowStr+"D"}); // 연산후 값, 바뀐 연산과정 큐에 넣기
        }
        if (!isVisit[S]) {
            isVisit[S] = true; // 방문표시
            q.push({ S, nowStr+"S"}); // 연산후 값, 바뀐 연산과정 큐에 넣기
        }
        if (!isVisit[L]) {
            isVisit[L] = true; // 방문표시
            q.push({ L, nowStr+"L"}); // 연산후 값, 바뀐 연산과정 큐에 넣기
        }
        if (!isVisit[R]) {
            isVisit[R] = true; // 방문표시
            q.push({ R, nowStr+"R"}); // 연산후 값, 바뀐 연산과정 큐에 넣기
        }
    }
}
 
int main() {
    int t,n, res;
    cin >> t;
    while (t--) {
        cin >> n >> res;
        fill(isVisit, isVisit + 10001, false); // 방문여부 초기화
        q = queue<struct n>(); // 큐 클리어(초기화)
        solve(n, res);
    }
}​