백준 9019 DSLR : bfs 활용 브루트포스 탐색 c++

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

9019번: DSLR

이 블로그에서 이전에 몇번 다뤄봤던 bfs 문제이다. (최단경로!)

여기서 중요한건 DSLR을 활용한 문자열을 출력해야 한다는 점이다. 이는 기존에 탐색 최소 횟수만을 세는 방식과는

살짝 푸는 아이디어를 달리 해야한다.(큰 아이디어는 같음.)

엄청 대단한건 아니고, 바꾼 상태의 문자를 저장하면서 게임을 진행해야 하기 때문에

벡터에다가 현재 숫자와 문자열을 쌍으로 저장해 둬야 진행하기 수월해지는 문제다.

 

<소스 코드>

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
int A,B;
bool visited[10001];
 
string bfs(void){
    queue<pair<int,string>> q;
    q.push(make_pair(A,""));
    visited[A] = true;
 
    while(!q.empty()){
        int num = q.front().first;
        string change = q.front().second;
        q.pop();
        if(num==B)
            return change;
        //D
        int newNum = (2*num)%10000;
        if(!visited[newNum]){
            visited[newNum]=true;
            q.push(make_pair(newNum,change+"D"));
        }
        //S
        newNum = num==0 ? 9999 : num-1;
        if(!visited[newNum]){
            visited[newNum]=true;
            q.push(make_pair(newNum,change+"S"));
        }
        //L
        int thousand = num/1000;
        int hundred = (num-1000*thousand)/100;
        int ten = (num-1000*thousand-100*hundred)/10;
        int one = (num-1000*thousand-100*hundred-10*ten);
        newNum = 1000*hundred + 100*ten + 10*one + 1*thousand;
        if(!visited[newNum]){
            visited[newNum]=true;
            q.push(make_pair(newNum,change+"L"));
        }
        //R
        newNum = 1000*one + 100*thousand + 10*hundred + 1*ten;
        if(!visited[newNum]){
            visited[newNum]=true;
            q.push(make_pair(newNum,change+"R"));
        }
    }
}
 
int main(void){
 
    int T;
    cin>>T;
    for(int i=0; i<T; i++){
        memset(visited,false, sizeof(visited));
        cin>>A>>B;
        cout<<bfs()<<"\n";
    }
}

<실행 결과>