백준 9019번 : DSLR (C++)

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

9019번: DSLR

 

코드

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
int DSLR(int now,char t)
{
    int next;
    if(t=='D')
    {
        next=now*2;
        if(next>9999) next=next%10000;
    }
    else if(t=='S')
    {
        if(now==0)next=9999;
        else next=now-1;
    }
    else if(t=='L')
    {
       next=(now*10+now/1000)%10000; 
    }
    else
    {
        next=now%10*1000+now/10;
    }
    return next;
}
int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    string str="DSLR";
    bool check[10000];
    queue<int> q;
    cin>>tc;
    while(tc--)
    {
        string m[10000];
        memset(check,false,sizeof(check));
        int a,b;
        cin>>a>>b;
        q.push(a);
        int ok=0;
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            for(int i=0;i<4;i++)
            {
                if(now==0 && i==0) continue;
                int next=DSLR(now,str[i]);
                if(!check[next])
                {
                    check[next]=true;
                    m[next]=m[now]+str[i];
                    if(b==next)
                    {
                        ok=1;
                        break;
                    }
                    q.push(next);
                }
            }
            if(ok)
            {   
                 q=queue<int>();
                  break;
            }
        }
        cout<<m[b]<<"\n";
    }
    return 0;
}

 

풀이

 bfs를 이용하여 최종값 b를 찾는 방법을 사용했는데 주의할 점은 숫자 0에서 D 명령을 수행하면 0*2=0으로 0에서 0으로 가는데 명령어 D를 사용한 것이 되기 때문에 50행의 if(now==0 && i==0) continue; 를 추가해줘야 한다. bfs를 수행하다가 최종값 b를 만나고 b로 만들어주는 명령어를 m 배열에 추가했다면 (55행) 이제 더는 bfs를 수행할 필요가 없기 때문에 ok변수를 이용해서 반복문을 빠져 나와준다. 이때 다음 테스트케이스를 위하여 큐를 초기화하여야 하는데 큐는 clear()가 없기 때문에  q=queue<int>(); 문장으로 큐를 재선언하여 비워줬다. (처음 써봄)

L명령과 R명령은 

L : next=(now*10+now/1000)%10000

R : next=now%10*1000+now/10 으로 간단하게 가능하다!