알고리즘

백준 9019 DSLR

중국고대사 2019. 4. 8. 17:17

한 번 연산할 때 출력할 문자열의 길이가 1증가 하므로 가중치가 1이라 할 수 있고, 필요한 최소 문자열의 길이를 구하는 것이므로 bfs로 풀 수 있다.

 

일단 string으로 문자열을 저장했더니 시간 초과가 났다. char로 저장해서 출력하자.

다음으로, 주석 친 부분처럼 l과 r연산을 했더니 틀렸다.

1000과 같이 0이 포함된 연산을 제대로 풀지 못해서 였다.

만약 처음 푼대로 l연산을 하면 16은 61이 된다. 하지만 16은 0016이므로 160이 되어야 한다.

 

덤벙대지 않고, 문제를 똑바로 보고 풀도록 하자!

 

따라서 코드는 아래와 같다.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <queue>
#include <cstring>
#include <stack>
using namespace std;
 
bool visit[10000];
char alpha[10000];
int from[10000];
 
int main(int argc, char** argv) {
    int t;
    cin >> t;
 
    while (t--) {
        int f, to;
        cin >> f >> to;
 
        memset(visit, false, sizeof(visit));
        memset(from, 0, sizeof(from));
        memset(alpha, 0, sizeof(alpha));
 
        queue<int> q;
        q.push(f);
        visit[f] = true;
 
        while (!q.empty()) {
            int val = q.front();
            //pop하는거 까먹지 말자!
            q.pop();
 
            //d연산
            int d = (val * 2) % 10000;
 
            if (!visit[d]) {
                q.push(d);
                visit[d] = true;
                from[d] = val;
                alpha[d] = 'D';
            }
 
            //s연산
            int s = val - 1;
            if (s == -1) s = 9999;
 
            if (!visit[s]) {
                q.push(s);
                visit[s] = true;
                from[s] = val;
                alpha[s] = 'S';
            }
 
            //l연산
            /*
            int l = val;
            int cnt = 1;
            while (l >= 10) {
                cnt *= 10;
                l /= 10;
            }
            l = (val % cnt) * 10 + l;
            */
            int l = (val % 1000) * 10 + val / 1000;    
            if (!visit[l]) {
                q.push(l);
                visit[l] = true;
                from[l] = val;
                alpha[l] = 'L';
            }
 
            //r연산
            /*
            int r = val / 10;
            r = (val % 10) * cnt + r;
            */
            int r = (val / 10) + (val % 10) * 1000;
            if (!visit[r]) {
                q.push(r);
                visit[r] = true;
                from[r] = val;
                alpha[r] = 'R';
            }
        }
 
        stack<char> s;
        while (f != to) {
            s.push(alpha[to]);
            to = from[to];
        }
        while (!s.empty()) {
            printf("%c", s.top());
            s.pop();
        }
        printf("\n");
    }
 
    return 0;
}
 cs