반응형

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

 

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. A와 B를 입력받아서 저장합니다.

 

2. 각 문자에 맞게 변환하는 함수를 만듭니다.

 

3. bfs를 돌며 string에 현재까지 입력된 명령어들을 저장하면서 queue에 넣어줍니다.

 

4. A 와 B가 같아지면 string을 출력합니다.

 

[ 소스코드 ]

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
79
80
81
82
83
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
struct node {
    int cur;
    string reg;
};
 
int left(int A)
{
    A *= 10;
    A += A / 10000;
    A %= 10000;
 
    return A;
}
 
int right(int A)
{
    int temp = A % 10;
    A /= 10;
    A += temp * 1000;
 
    return A;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int A, B;
        int visited[10000] = { 0 };
 
        scanf("%d %d", &A, &B);
 
        queue<node> q;
        string vect;
 
        q.push({ A,  vect});
        visited[A] = 1;
 
        while (!q.empty()) {
            int cur = q.front().cur;
            string str = q.front().reg;
            q.pop();
 
            if (cur == B) {
                for (auto next : str) {
                    printf("%c", next);
                }
                printf("\n");
                break;
            }
 
            vector<char> temp;
            int l = left(cur);
            int r = right(cur);
            int d = (cur * 2) % 10000;
            int s = (cur + 9999) % 10000;
            if (visited[l] != 1) {
                visited[l] = 1;
                q.push({ l, str+'L'});
            }
            if (visited[r] != 1) {
                visited[r] = 1;
                q.push({ r, str+'R'});
            }
            if (visited[d] != 1) {
                visited[d] = 1;
                q.push({ d, str+'D'});
            }
            if (visited[s] != 1) {
                visited[s] = 1;
                q.push({s, str+'S'});
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10

+ Recent posts

티스토리툴바