[C++] 백준 9019번: DSLR

🔍문제

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

9019번: DSLR

 

📝 풀이

자릿수의 변화에 당황하지 않는다면 쉽게 풀 수 있다!

자릿수가 변화에 맞는 식을 아래와 같이 세워줍니다.

D = num * 2 % 10000;
S = (num == 0 ? 9999 : num-1);
L = num % 1000 * 10 + num / 1000;
R = num % 10 * 1000 + num / 10;

전형적인 queue를 이용한 BFS로 풀되, command를 저장하기 위한 컨테이너를 골라줍니다. 컨테이너는 특정 숫자가 어떤 명령어들을 통해 나왔는지 저장하는 용도입니다.

• pair
• class
• struct

위 대충 int랑 string만 저장하면 그만이지만 그냥 class랑 struct 두 버전으로 풀어봤습니다.

 

struct

struct pair
{
public:
    int num;
    std::string str;
};

 

💾 소스

알고리즘푸는데 클래스는 오버하는 것 같아서 구조체로 푼 코드만 올리겠습니다.

메모리나 시간도 struct가 더 빠르네요~

 

#include <iostream>
#include <string>
#include <queue>
#include <memory.h>
#define MAX 10001

int A, B;

struct pair
{
public:
    int num;
    std::string str;
};

std::string BFS()
{
    std::queue<pair> q;
    bool visited[MAX] = {false, };
    q.push({A, ""});
    visited[A] = true;
    
    int temp = 0;
    while(!q.empty())
    {
        int num = q.front().num;
        std::string command = q.front().str;
        q.pop();
        
        if(num == B)
        {
            return command;
        }
        
        //D
        temp = (num * 2) % 10000;
        if(!visited[temp])
        {
            visited[temp] = true;
            q.push({temp, command+"D"});
        }
        
        //S
        temp = (num == 0 ? 9999 : num-1);
        if(!visited[temp])
        {
            visited[temp] = true;
            q.push({temp, command+"S"});
        }
        
        //L
        temp = num % 1000 * 10 + num / 1000;
        if(!visited[temp])
        {
            visited[temp] = true;
            q.push({temp, command+"L"});
        }
        
        //R
        temp = num % 10 * 1000 + num / 10;
        if(!visited[temp])
        {
            visited[temp] = true;
            q.push({temp, command+"R"});
        }
        
    }
    
    return "";
}

int main()
{
    int T; std::cin >> T;
    while(T--)
    {
        std::cin >> A >> B;
        std::cout << BFS() <<'\n';
    }
    return 0;
}