[백준OJ] 9019번 DSLR

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

9019번: DSLR

---

 

 

풀이

BFS를 이용하였다. BFS를 이용해서 처음 입력받은 수를 각각 D,S,L,R 을 시행했을때, 변환된 숫자가 한번도 나오지 않은 숫자라면, 큐에 추가해주며 최단거리로 바꿔야 하는 숫자에 도달했을때, 그 바뀐 로그를 출력해주면 된다.

 

시간복잡도

BFS알고리즘이므로, 최악으로 0~10000까지 모두 탐색을 해서 맞추는것이므로, O(1)이 된다.

 

반응형

코드

#include<iostream>
#include<queue>
#include<string>

using namespace std;

void bfs(int a,int b){
    bool visited[10001]={0};
    queue<pair<int,string>> q;
    q.push({a,""});
    visited[a]=true;
    
    while(!q.empty()){
        int now=q.front().first;
        string now_str=q.front().second;
        q.pop();
        
        if(now==b){
            cout<<now_str<<"\n";
            return;
        }
        
        int D=(now*2)%10000;
        if(!visited[D]){
            visited[D]=true;
            q.push({D,now_str+"D"});
        }
        
        int S=(now-1<0?9999:now-1);
        if(!visited[S]){
            visited[S]=true;
            q.push({S,now_str+"S"});
        }
        
        int L=(now%1000)*10+(now/1000);
        if(!visited[L]){
            visited[L]=true;
            q.push({L,now_str+"L"});
        }
        
        int R=(now%10)*1000+(now/10);
        if(!visited[R]){
            visited[R]=true;
            q.push({R,now_str+"R"});
        }
    }
}

int main() {
	
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        bfs(a,b);
    }
    
	return 0;
}