[백준/BOJ] 9019 DSLR - 접근과 풀이 (c++)

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

9019번: DSLR

bfs + 백트래킹 감잡기 문제.

 

 

---

접근 방법

 

D, S, R, L 변환 방법으로 특정 숫자에 최단으로 도달하고, 도달 방법을 찾는 문제이다. bfs를 이용하면 최단 길이는 어렵지 않게 구할 수 있고, 변환 방법을 기억해야한다. bfs를 돌릴 때 큐에 변환된 과정을 넣으면 메모리가 초과될 것 같으므로, num1 -> num2로 변환될 때 num2에서 num1으로 돌아갈 수 있도록 어떤 숫자에서 변환이 되었는지와 변환된 방법을 기록한다. 

 

dfs든 bfs든 백트래킹에서 가장 핵심적인 내용이 아마 굵은 글씨로 표현한 것이 아닌가 싶음. 돌아갈 수 있는 길을 만들어 놓는 것.

 

---

풀이

 

tag : bfs, back-tracking

 

#include<iostream>
#include<queue>
#include<string.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int T,A,B;
int visitedFrom[10001];
int convertedBy[10001];
int DSLR(char ch, int num){
  if(ch==0){ //D
    return num*2%10000;
  }
  else if(ch==1) { //S
    return (num+9999) %10000;
  }
  else if(ch==2) { //L
    return (num%1000 *10) + (num/1000);
  }
  //R
  return (num%10 *1000) + (num/10);
  
}
void backTrack(){
  int num=B;
  char dslr[4]={'D','S','L','R'};
  vector<char> ans;
  while(num!=A){
    ans.push_back(dslr[convertedBy[num]]);
    num=visitedFrom[num];
  }
  int vs=ans.size();
  for(int i=vs-1;i>=0;i--)
    cout<<ans[i];
  cout<<endl;
}
void bfs(){
  queue<int> q;
  int depth=0;
  q.push(A);
  visitedFrom[A]=-2;

  while(!q.empty()){
    int qs=q.size();
    for(int i=0;i<qs;i++){
      int deq=q.front();
      q.pop();
      if(deq==B){
        backTrack();
        return;
      }
      for(int j=0;j<4;j++){
        int conv=DSLR(j,deq);
        if(visitedFrom[conv]==-1){
          visitedFrom[conv]=deq;
          convertedBy[conv]=j;
          q.push(conv);
        }
      }
    }
    depth++;
  }
}
int main(){
  cin>>T;
  while(T--){
    memset(visitedFrom,-1,sizeof(visitedFrom));
    memset(convertedBy,-1,sizeof(convertedBy));
    cin>>A>>B;
    bfs();
    cout<<endl;
  }
}

추가로, 큐에 넣는 것을, string으로 넣으면 메모리초과가 안날수도 있을 것 같다. 

참고로 10000^2 의 모든 변환과정에서 최대 횟수를 찾아보려 했는데, 14번정도 인듯