bfs문제였다.
최단경로 => BFS !
그리고 path reconstruct할때 reverse하는거 잊지말자!
/**
* @name: DSLR
* @link: https://www.acmicpc.net/problem/9019
* @date 2020-04-30
* @author sunmon
* TIP: String으로 이용
**/
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int parent[10000];
string DSLR[4] = {"D","S", "L", "R"};
int dslr(int n, int t){
if(t == 0) return (n<<1) % 10000;
else if(t == 1) return (n==0)? 9999: n-1;
else if(t == 2) return (n%1000)*10 + n/1000;
else return n/10 + (n%10)*1000;
}
string solve(int a, int b){
queue<int> q;
q.push(a);
parent[a] = a; //주의! 이거 없으면 무한뺑뺑이 가능
while(!q.empty()){
int cur = q.front();
q.pop();
if(cur == b) break;
for(int i = 0; i<4; i++){
int next = dslr(cur, i);
if(parent[next]!=-1) continue;
parent[next] = cur;
q.push(next);
}
}
//construct
string path="";
int cur = b;
while(cur != parent[cur]){
int next = parent[cur];
for(int i = 0; i<4; i++){
if(dslr(next, i) != cur) continue;
path += DSLR[i];
break;
}
cur = next;
}
reverse(path.begin(), path.end());
return path;
}
int main(){
int t;
cin >> t;
while(t--){
memset(parent,-1,sizeof(parent));
int a, b;
cin >> a >> b;
cout << solve(a,b) << "\n";
}
}
'Study > Algorithm' 카테고리의 다른 글
[백준 #9663] N-Queen (0) | 2020.05.05 |
---|---|
백준 #1963 : 소수경로 (0) | 2020.05.04 |
[백준] #10844 쉬운계단수 (0) | 2020.04.15 |
코딩테스트에서 신경쓸 것 (1) | 2020.04.05 |
코 드 조 아 (0) | 2019.11.17 |