[백준 9019번] DSLR (C++)

문제링크 : https://www.acmicpc.net/problem/9019

9019번: DSLR

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int A, B;
int D, S, L, R;
bool visited[10000];

void bfs()
{
    queue<pair<int, string>> q;
    q.push({A, ""});
    visited[A] = 1;

    while(!q.empty())
    {
        auto [num, str] = q.front();
        q.pop();

        if(num == B)
        {
            cout << str << "\n";
            return;
        }

        D = (num * 2) % 10000;
        if(!visited[D])
        {
            visited[D] = 1;
            q.push({D, str + "D"});
        }

        S = (num == 0) ? 9999 : num - 1;
        if(!visited[S])
        {
            visited[S] = 1;
            q.push({S, str + "S"});
        }

        L = num % 1000 * 10 + num / 1000;
        if(!visited[L])
        {
            visited[L] = 1;
            q.push({L, str + "L"});
        }

        R = num / 10 + num % 10 * 1000;
        if(!visited[R])
        {
            visited[R] = 1;
            q.push({R, str + "R"});
        }

    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while(T--)
    {
        cin >> A >> B;
        memset(visited, 0, sizeof(visited));
        bfs();
    }

    return 0;
}

크게 설명할것은 없는 문제다.

BFS이기는 한데 조금 다른 느낌이다.

 

큐를 int와 string으로 두고 각 계산을 통해서 만들어진 DSLR과 각 문자를 입력받는 것이 핵심이다.

처음에 방문 체크를 안하고 풀었다가 메모리 초과가 났다.