백준 9019번 DSLR

🔒[문제 url]

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

🔑알고리즘

전형적인 BFS에서 방향만 상하좌우가 아닌 D S L R로 바뀐 문제이다.

• DSLR을 어떻게 구현하는가?
  • D : $n$을 2배하고 10000으로 나눈다 하였으므로, $n_i = 2\times n_{i-1} \ mod \ 10000$
  • S : $n_i= \begin{cases} n_{i-1}-1,\;if\;n_{i-1}>0\\ 9999,\;if\;n_{i-1} =0 \end{cases}$
  • L : $n_i = 10\times (n_{i-1}\mod\ 1000)+(n_{i-1} \ /\ 1000)$
  • R : $n_i = (n_{i-1} \ / \ 10) + 1000 \times (n_{i-1}\ mod \ 10)$
    
    
• 명령어는 어떻게 출력할까?
  • BFS 탐색시, queue에 실행한 명령또한 push하여 B가 되었을 때에 출력한다.

🐾부분 코드

struct dslr
{
    int num;
    string cmd;
};

<dslr 구조체 정의>
BFS 탐색시 queue에 담을 정보를 구조체로 선언한다.
num : 은 명령어 실행 후 값
cmd : 현재까지 실행된 명령어

/* DSLR fuc start*/
int D(int a)
{
    return 2 * a % 10000;
}
int S(int a)
{
    if (a != 0) return a - 1;
    else return 9999;
}
int L(int a)
{
    return 10 * (a % 1000) + (a / 1000);
}
int R(int a)
{
    return (a / 10) + 1000 * (a % 10);
}
/* DSLR fuc end*/

<명령어 구현 함수>
위에서 설명한 알고리즘과 동일하다.

string BFS(int a, int b)
{
    queue<dslr> q;
    q.push({ a,"" });
    visited[a] = 0;

    while (!q.empty())
    {
        dslr now = q.front();
        q.pop();

        dslr next[4] = {{ D(now.num), now.cmd + "D" },
                        { S(now.num), now.cmd + "S" },
                        { L(now.num), now.cmd + "L" },
                        { R(now.num), now.cmd + "R" } };
        for (int i = 0; i < 4; i++)
        {
            
            if (visited[next[i].num] == 0)
            {
                q.push(next[i]);
                visited[next[i].num] = visited[now.num] + 1;
            }
            
            if (next[i].num == b)
            {
                return next[i].cmd;
            }
        }// for end


    }
}

<BFS 함수>

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <string>
#include <memory.h> // memset
// 자료 구조
#include <queue>
using namespace std;

int t, a, b;
int visited[10000];
struct dslr
{
    int num;
    string cmd;
};

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
}

/* DSLF fuc start*/
int D(int a)
{
    return 2 * a % 10000;
}
int S(int a)
{
    if (a != 0) return a - 1;
    else return 9999;
}
int L(int a)
{
    return 10 * (a % 1000) + (a / 1000);
}
int R(int a)
{
    return (a / 10) + 1000 * (a % 10);
}
/* DSLR fuc end*/

string BFS(int a, int b)
{
    queue<dslr> q;
    q.push({ a,"" });
    visited[a] = 0;

    while (!q.empty())
    {
        dslr now = q.front();
        q.pop();

        dslr next[4] = {{ D(now.num), now.cmd + "D" },
                        { S(now.num), now.cmd + "S" },
                        { L(now.num), now.cmd + "L" },
                        { R(now.num), now.cmd + "R" } };
        for (int i = 0; i < 4; i++)
        {
            
            if (visited[next[i].num] == 0)
            {
                q.push(next[i]);
                visited[next[i].num] = visited[now.num] + 1;
            }
            
            if (next[i].num == b)
            {
                return next[i].cmd;
            }
        }// for end


    }
}
void SOLVE()
{
    while (t--)
    {
        cin >> a >> b;

        cout << BFS(a, b) << "\n";
        memset(visited, 0, sizeof(visited));
    }

}



int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

So easy하게 풀었다. DFS/BFS 문제는 이제 꽤나 자신이 있다.
며칠 후 플3 BFS에 처참히 깨질 망자의 기록입니다.