[C++] BOJ 9019 - DSLR

BOJ 9019 - DSLR (https://www.acmicpc.net/problem/9019)

 

01. 🔎 문제 탐색

D: n을 2배로 하여 10000으로 모듈러 연산한 값을 레지스터에 저장
S: n-1을 레지스터에 저장. 단, n이 0일 경우 9999를 레지스터에 저장
L: 각 자리수를 왼쪽으로 회전 (d1d2d3d4 -> d2d3d4d1)
R: 각 지리수를 오른쪽으로 회전 (d1d2d3d4 -> d4d1d2d3)

INPUT
T: 테스트케이스 개수
A: 시작 숫자, B: 목표 숫자

OUTPUT
A를 B로 바꾸기 위한 최소한의 명령을 출력

01-1. 가능한 시간 복잡도

• 최대 10000번의 연산, 시간 복잡도 O(N)으로 구현

01-2. 알고리즘 선택

• 시작 상태 A에서 D, S, L, R 4개의 명령으로 B를 만드는 것으로 BFS를 통해 최단 명령어를 구할 수 있음

02. 📝 코드 설계하기

1. A, B를 입력
2. 각 위치에 도달한 명령어의 최소 개수를 저장하는 vector와 이미 방문한 위치인지 확인하는 vector를 선언
3. A부터 시작하므로, A를 queue에 담아주고, 방문 처리
4. queue의 가장 앞의 원소를 꺼냄
5. 원소를 기준으로 D, S, L, R의 명령어를 수행
6. 각 명령의 결과로 나온 위치가 이미 방문한 위치인지 확인하고, 이미 방문한 위치라면 무시
7. 방문한 위치가 아니라면, 방문 처리 후, 결과로 나온 위치를 방문처리하고 명령어를 이전 명령어에 합쳐 vector에 누적 저장
8. 결과 위치를 queue에 추가하고, queue의 요소를 모두 꺼낼 때까지 4번부터 반복

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

string solution(int A, int B){
  vector<string> graph(10000, "");
  vector<bool> visited(10000, false);

  queue<int> q;
  
  q.push(A);
  visited[A] = true;
  
  while(!q.empty()){
    int cur = q.front(); q.pop();
    string prev_order = graph[cur];
    char dir[4] = {'D', 'S', 'L', 'R'};
    
    int reg;
    for(auto& e : dir){
      if(e == 'D') reg = (2*cur) % 10000;
      else if(e == 'S') reg = (cur == 0 ? 9999 : cur-1);
      else if(e == 'L') reg = (cur % 1000) * 10 + (cur / 1000);
      else if(e == 'R') reg = (cur % 10) * 1000 + (cur / 10);

      if(visited[reg]) continue;
      
      visited[reg] = true;
      graph[reg] = (prev_order + e);
      q.push(reg);
    }
  }

  return graph[B];
}

int main(){
  ios::sync_with_stdio(0); cin.tie(0);

  int T;
  int A, B;
  cin >> T;

  while(T--){
    cin >> A >> B;
    cout << solution(A, B) << "\n";
  }

  return 0;
}