BOJ 9019

19 Mar 2020 • ProblemSolving

DSLR

문제출처

문제 해석

  • 주어진 A 숫자를 B숫자로 변환하기 위해 필요한 최소 연산 수를 구하는 문제입니다.
  • 가능한 연산은 다음과 같습니다.
    1. D: 2배로 바꿉니다. 9999를 초과하지 않게 합니다 => (2xn)%10000
    2. S: n-1을 레지스터에 저장합니다. n이 0이라면 9999가 대신 레지스터에 저장됩니다.
    3. L: n의 각 자릿수를 왼쪽으로 한번 회전시킵니다.
    4. R: n의 각 자릿수를 오른쪽으로 한번씩 회전시킵니다.

설계(10)

  • 각 숫자를 한번씩만 방문하고 최소연산수를 찾기 위해서 BFS를 이용합니다.
  • 각 연산(D,S,L,R)마다 다음 숫자는 {(nx2)%10000,(n-1or9999),(n%1000)x10+n/1000,n/10+(n%10)x1000}로 변환됩니다.
  • 해당 문제에서 요구하는 정답은 최소 연산수가 아니라, 어떤 연산을 사용하였는가 이기 때문에 연산의 경로를 저장하는 path배열을 사용합니다.
  • path배열은 이전 경로와 연결을 시켜주며, 어떤 연산을 사용했는지에 대한 정보가 저장되어있습니다.
  • 원하는 B숫자가 나온 경우, path배열을 역추적하여 ans에 저장한 후, 반대로 출력을 시켜주면 됩니다.

구현(40)

코드
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 10000

bool visited[MAXN];
queue<int> q;
pair<int,int> path[MAXN];
int N;
int A,B;
string order ="DSLR";


string bfs(){
    visited[A] = true;
    q.push(A);
    while (!q.empty()){
        int q_size = q.size();
        while (q_size--){
            int cur = q.front();
            if(cur == B) {
                string ans = "";
                while (path[cur].second!=-1){
                    ans+= order[path[cur].second];
                    cur = path[cur].first;
                }
                reverse(ans.begin(),ans.end());
                return ans;
            }
            q.pop();
            //D
            int next_num = (cur*2)%MAXN;
            if (!visited[next_num]){
                visited[next_num] = true;
                path[next_num] = {cur,0};
                q.push(next_num);
            }
            //S
            if (cur ==0) next_num = 9999;
            else next_num = cur-1;
            if (!visited[next_num]){
                visited[next_num] = true;
                path[next_num] = {cur,1};
                q.push(next_num);
            }
            //L
            next_num = (cur%1000)*10+cur/1000;
            if (!visited[next_num]){
                visited[next_num]= true;
                path[next_num] = {cur,2};
                q.push(next_num);
            }
            //R
            next_num = cur/10+(cur%10)*1000;
            if (!visited[next_num]){
                visited[next_num] = true;
                path[next_num] = {cur,3};
                q.push(next_num);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    while (N--){
        memset(path,-1,sizeof(path));
        memset(visited,false,sizeof(visited));
        while (!q.empty()) q.pop();
        cin >> A >> B;
        cout << bfs() <<"\n";
    }
    return 0;
}
디버깅
  • 처음에 구현할 때, 숫자를 string형으로 받아서 구현했지만 시간초과가 나왔습니다.
  • 또한, 큐에 각 경로를 저장하게 구현을 해서 시간초과를 하는데 한 몫한 것 같습니다.
  • 시간을 최적화시키기 위해서 숫자를 int형으로 변환시켰으며, path배열에 경로를 저장한 후 역추적해서 찾는 방식으로 바꿔서 구현하였습니다.
  • 한가지 실수한 부분은 S연산을 할 때, n-1 == 0 이면 9999로 변환되게 잘못 구현하였습니다.(지문을 잘못이해하였습니다)
제출결과
  • 1148ms

마무리

  • BFS를 활용한 문제였습니다. 문제 자체는 그리 어렵지 않지만 구현을 하는데 실수한 부분들이 많았습니다.
 BOJ

Related Posts