[백준 / BOJ / GOLD 5] 9019 번 : DSLR

지나가던 개발자 2020. 4. 10. 21:24

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

9019번: DSLR

문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경

www.acmicpc.net

문제 접근법

입력 값과 명령어를 저장할 queue를 만든다.
4가지 명령어를 수행할 때 방문을 체크하기 위하여 bool 값 배열을 준비한다.
방문한 적이 없을 때 해당하는 명령어를 실행한다.
실행했을 때 숫자값과 명령어를 queue에 넣는다.
숫자가 원하던 값과 일치하면 명령어를 출력한다.

아래는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
bool visit[10001];
 
string Bfs(int a, int b)
{
    queue<pair<int, string>> q;
    q.push(make_pair(a, ""));
 
    while (!q.empty())
    {
        int n = q.front().first;
        string dslr = q.front().second;
        q.pop();
 
        if (n == b)
        {
            return dslr;
        }
 
        int num;
        num = (n * 2) % 10000;
 
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "D"));
        }
 
        num = n == 0 ? 9999 : n - 1;
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "S"));
        }
 
        num = (n % 1000) * 10 + (n / 1000);
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "L"));
        }
 
        num = (n % 10) * 1000 + (n / 10);
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "R"));
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int a;
 
    cin >> a;
 
    for (int i = 0; i < a; i++)
    {
        int b, c;
 
        cin >> b >> c;
        cout << Bfs(b, c) << "\n";
 
        memset(visit, false, sizeof(visit));
    }
 
    return 0;
}
Colored by Color Scripter

 