https://www.acmicpc.net/problem/9019
9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
www.acmicpc.net
0000부터 9999까지 정점이 10000개
10000개는 그렇게 큰 숫자가 아니므로 BFS 사용 가능
경로 구하는 문제? 숨바꼭질 4
https://www.acmicpc.net/problem/13913
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
from 배열과 how 배열을 사용해
재귀를 사용하든 아니면 역추적해서 reverse 하든지!
|
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
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
bool check[10001];
int dist[10001];
char how[10001];
int from[10001];
void print(int n, int m)
{
if (n == m) return;
print(n, from[m]); //재귀를 쓰면 역순을 할 필요가 없다
cout << how[m];
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
memset(check, 0, sizeof(check));
memset(dist, 0, sizeof(dist));
memset(how, 0, sizeof(how));
memset(from, 0, sizeof(from));
check[n] = true;
dist[n] = 0;
from[n] = -1;
queue<int> q;
q.push(n);
while (!q.empty())
{
int now = q.front();
q.pop();
int next = 2 * now % 10000;
if (check[next] == false)
{
q.push(next);
check[next] = true;
dist[next] = dist[now] + 1;
from[next] = now;
how[next] = 'D';
}
if (now == 0)
next = 9999;
else
next = now - 1;
if (check[next] == false)
{
q.push(next);
check[next] = true;
dist[next] = dist[now] + 1;
from[next] = now;
how[next] = 'S';
}
next = (now % 1000) * 10 + now / 1000;
if (check[next] == false)
{
q.push(next);
check[next] = true;
dist[next] = dist[now] + 1;
from[next] = now;
how[next] = 'L';
}
next = (now % 10) * 1000 + (now / 10);
if (check[next] == false)
{
q.push(next);
check[next] = true;
dist[next] = dist[now] + 1;
from[next] = now;
how[next] = 'R';
}
}
//print(n, m);
//cout << '\n';
string ans = "";
while (m != n)
{
ans += how[m];
m = from[m];
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
return 0;
}
|
cs |