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
|
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
int T;
int A, B;
char chk[10001];
int cchk[10001];
struct Data {
int n;
};
stack<char>s;
int L_play(int n) {
int num[4];
for (int i = 0, ten = 1000; i < 4; i++, ten /= 10) {
num[i] = n / ten;
n %= ten;
}
int first = num[0];
for (int i = 1; i < 4; i++) {
num[i - 1] = num[i];
}
num[3] = first;
first = 0;
for (int i = 0, ten = 1000; i < 4; i++, ten /= 10) {
first += num[i] * ten;
}
return first;
}
int R_play(int n) {
int num[4];
for (int i = 0, ten = 1000; i < 4; i++, ten /= 10) {
num[i] = n / ten;
n %= ten;
}
int first = num[3];
for (int i = 2; i >= 0; i--) {
num[i + 1] = num[i];
}
num[0] = first;
first = 0;
for (int i = 0, ten = 1000; i < 4; i++, ten /= 10) {
first += num[i] * ten;
}
return first;
}
void init() {
scanf("%d %d", &A, &B);
memset(chk, 0, sizeof(chk));
memset(cchk, 0, sizeof(cchk));
}
void bfs() {
queue<Data>q;
q.push({ A });
while (!q.empty()) {
Data c = q.front(); q.pop();
if (c.n == B) {
//for (int i = 0; i < c.a.size(); i++) {
// printf("%c", c.a[i]);
//}
//printf("\n");
return;
}
for (int i = 0; i < 4; i++) {
Data n = c;
if (i == 0) {//D
n.n = (n.n * 2) % 10000;
if (chk[n.n] ==0) {
cchk[n.n] = c.n;
chk[n.n] = 'D';
q.push(n);
}
}
else if (i == 1) {//S
n.n = (n.n + 9999) % 10000;
if (chk[n.n] ==0) {
cchk[n.n] = c.n;
chk[n.n] = 'S';
q.push(n);
}
}
else if (i == 2) {//L
n.n = L_play(n.n);
if (chk[n.n] == 0) {
cchk[n.n] = c.n;
chk[n.n] = 'L';
q.push(n);
}
}
else if (i == 3) {//R
n.n = R_play(n.n);
if (chk[n.n] ==0) {
cchk[n.n] = c.n;
chk[n.n] = 'R';
q.push(n);
}
}
}
}
}
int main(void) {
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++) {
init();
bfs();
while (1) {
if (B== A)break;
s.push(chk[B]);
// printf("%c", chk[B]);
B = cchk[B];
}
while (!s.empty()) {
printf("%c", s.top());
s.pop();
}
printf("\n");
}
}
|
이문제는 어떻게 보면 쉬운데 시간초과 가 많이 생길 수 있습니다.
저도 처음에는 백터를 가지고 경로를 저장을 하면서 큐에 넣었었는데 그렇게 되면 솔직히 답을 도출하기에는 쉬운데
느릴 수있으니 다른배열에 경로는 넣어놓고 인덱스로 찾아서 가면 되는데 말로만 말하면 이해가 안될 수 있기 때문에
그림으로 설명해 드리겠습니다.
1번 배열 큐를 돌면 숫자를 인덱스로 하고 그것에 따라 쓴 명령어를 입력해 놓습니다.
2번 배열 시작한 숫자를 인덱스로 두고 바뀐 숫자를 배열값으로 하여 입력을 해놓습니다. 그이유는
만약에 1번 배열을 chk 라고 하고
2번 배열을 cchk 라고 한다면
이렇게 입력이됩니다.
chk[2468]=1234; cchk[2468] ='D';
chk[2341]=1234; cchk[2341] ='L';
chk[4123]=1234; cchk[4123] ='R';
이렇게 입력이 되어야 합니다. 그이유는 아래에서 설명해 드리겠습니다.
위에 소스를 보게되면 3412인 인덱스부터 스택에 넣었는데 그이유는 1234로 시작하면 2468 과 2341, 4123 이라는 선택지가 3개가 있습니다. 그렇게 되면
위에 chk 글 보면 1234라는 선택지가 3개가 되어 찾아갈수도 없고 4123이 찾아야하는경로라고 하면
4123이 왔던 경로를 찍힐수 있도록 했기때문에 끝에서부터 B가 4213이라면
chk[4213]의 'R"을 저장하고 그리고 다음에 chk[4213]에 저장된 1234를 인덱스로 쓰기위해서
cchk[chk[4213]] 이렇게 하시면 cchk[1234] 와 같은 의미로 경로를 저장할수 있습니다.
거꾸로 해서 경로는 저장했기때문에 일부로 스택이라는 자료구조로 나중에 들어간 경로 즉, 처음 출발하는 경로이기때문에 사용했습니다. 그렇게 스택의 top부분부터 빼면서 출력하면 답이 됩니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 6087 레이저 통신 (0) | 2019.09.19 |
|---|---|
| 백준 16918 봄버맨 (0) | 2019.09.17 |
| 백준 2638 치즈 (0) | 2019.09.17 |
| 백준 1726 로봇 (0) | 2019.09.17 |
| 백준 2468 안전영역 (0) | 2019.09.17 |
댓글