백준 9019 : DSLR

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

---

문제

4자리 수를 가지고 다른 자연수 만드는 방식

DSLR 4가지의 명령어로 숫자 수정가능

D : 수를 2배로 만든다 9999 넘어가면 10000의 나머지로 대체한다

S : 수에서 1을 뺀다 수가 -1이 되면 9999로 대체한다

L : 자릿수를 왼쪽으로 회전 (1234 -> 2341)

R : 자릿 수를 오른쪽으로 회전 (1234 -> 4123)

숫자 2개가 주어질때 가장 작은 명령으로 도달하게 만들어라   

---

생각

1.  일단 BFS다
2. 명령을 어떻게 가지고 있어야 하나 고민 -> pair로 들고 있게 만들자
3. 회전 쪽에서 고민 -> 자릿수를 나누고 더하고 해서 어떻게든 하자
4. 가장 먼저 도착하면 그냥 나머지는 무시하게 하자

---

코드

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

using namespace std;

int main()
{
    int n;
    std::cin >> n;

    for(int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;

        queue<pair<int, string>> q;
        q.push({a, ""});

        while(!q.empty())
        {
            auto current = q.front();
            int cur = current.first;
            string ops = current.second;
            q.pop();

            if(cur == b)
            {
                cout << ops << "\n";
                break;
            }

            int D = (cur * 2) % 10000;
            int S = (cur == 0) ? 9999 : cur - 1;
            int L = (cur % 1000) * 10 + (cur / 1000);
            int R = (cur % 10) * 1000 + (cur / 10);
            
            q.push({D, ops + "D"});
            q.push({S, ops + "S"});
            q.push({L, ops + "L"});
            q.push({R, ops + "R"});
        }
    }
}

---

틀린 이유

• 메모리 초과
• 아마 q에 중복된(이미 계산된) 데이터가 들어가서 그런거 같음

---

수정 코드

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

using namespace std;

int main()
{
    int n;
    std::cin >> n;

    for(int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;

        queue<pair<int, string>> q;

        vector<bool> visited(10000, false);

        q.push({a, ""});
        visited[a] = true;

        while(!q.empty())
        {
            auto current = q.front();
            int cur = current.first;
            string ops = current.second;
            q.pop();

            if(cur == b)
            {
                cout << ops << "\n";
                break;
            }

            int D = (cur * 2) % 10000;
            int S = (cur == 0) ? 9999 : cur - 1;
            int L = (cur % 1000) * 10 + (cur / 1000);
            int R = (cur % 10) * 1000 + (cur / 10);
            
            if(!visited[D])
            {
                q.push({D, ops + "D"});
                visited[D] = true;
            }

            if(!visited[S])
            {
                q.push({S, ops + "S"});
                visited[S] = true;
            }

            if(!visited[L])
            {
                q.push({L, ops + "L"});
                visited[L] = true;
            }
            
            if(!visited[R])
            {
                q.push({R, ops + "R"});
                visited[R] = true;
            }
        }
    }
}

---

결과

• 문제 풀이 시간 : 28분
• 메모리 :  2156 KB
• 시간 :  3732 ms

  ---

배운점 및 고칠점

• 중복 체그좀 하자
• 문자열 복사는 생각이상으로 무겁다 -> More effective Cpp 에서 배웠자너
• 문자열을 int로 바꾸지 말고 int로 관리 가능한것은 숫자로 관리하자
• 삼향연산자좀 써보자