백준 9019 DSLR - C++, 큐를 이용한 너비 우선 탐색

9019 : www.acmicpc.net/problem/9019

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

int t, a, b, cur, nextNum;
queue<char> q;
bool visit[100001];

string bfs(){
    queue<pair<int, string>> q;
    q.push(make_pair(a, ""));
    visit[a] = true;

    while(!q.empty()){
        int cur = q.front().first;
        string s = q.front().second;
        q.pop();

        if(cur == b)
            return s;
        
        // D : 2n mod 10000
        nextNum = (2 * cur) % 10000;
        if(!visit[nextNum]){
            visit[nextNum] = true;
            q.push(make_pair(nextNum, s + "D"));
        }
        // S : n -1 (n=0이라면 9999)
        nextNum = (cur-1) < 0 ? 9999 : cur-1;
        if(!visit[nextNum]){
            visit[nextNum] = true;
            q.push(make_pair(nextNum, s + "S"));
        }
        // L : 각 자리수 왼쪽으로   1234  2341
        nextNum = (cur % 1000) * 10 + (cur / 1000);
        if(!visit[nextNum]){
            visit[nextNum] = true;
            q.push(make_pair(nextNum, s + "L"));
        }
        // R : 각 자리수 오른쪽으로   1234  4123
        nextNum = (cur / 10) + ((cur%10) * 1000);
        if(!visit[nextNum]){
            visit[nextNum] = true;
            q.push(make_pair(nextNum, s + "R"));
        }
    }
}

int main(){
    scanf("%d", &t);

    while(t--){
        memset(visit, false, sizeof(visit));
        scanf("%d %d", &a, &b);
        cout << bfs() << '\n';
    }
}

---

 금방 풀 수 있는 BFS 문제인데 queue에 pair을 넣어야 한다는 생각이 안나서 조금 오래 걸렸습니다. 큐에 들어가는 값은 연산이 끝난 수와 지금까지의 연산을 기록하는 문자열으로 먼저 나오는 값을 뱉어내면 되니 큐에 순서에 관계 없이 넣어도 됩니다. (어느 레벨에서 연산이 끝났는지가 중요)