코딩테스트/문제
[백준] 9019번 DSLR
스키(ski)
2022. 9. 3. 16:17
문제 내용
https://www.acmicpc.net/problem/9019
9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
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
|
#include <iostream>
#include <queue>
#include <string.h> //memset 사용을 위한 header
#include <tuple> //tie 사용을 위한 header
#define MAX_N 10000
using namespace std;
bool visited[MAX_N];
int D(int n) {
int a = 2 * n;
if (a >= MAX_N)
a %= MAX_N;
return a;
}
int S(int n) {
if (n == 0)
return 9999;
return n - 1;
}
int L(int n) { return (n % 1000) * 10 + (n / 1000); }
int R(int n) { return (n / 10) + (n % 10) * 1000; }
string BFS(int start, int end) {
queue<pair<int, string>> q;
q.push(make_pair(start, ""));
visited[start] = true;
while (!q.empty()) {
int a;
string b;
tie(a, b) = q.front();
q.pop();
if (a == end) {
return b;
}
int d, s, l, r;
d = D(a);
s = S(a);
l = L(a);
r = R(a);
if (!visited[d]) {
q.push(make_pair(d, b + "D"));
visited[d] = true;
}
if (!visited[s]) {
q.push(make_pair(s, b + "S"));
visited[s] = true;
}
if (!visited[l]) {
q.push(make_pair(l, b + "L"));
visited[l] = true;
}
if (!visited[r]) {
q.push(make_pair(r, b + "R"));
visited[r] = true;
}
}
}
int main() {
// 72~73:입출력 시간을 단축하기 위한 코드
cin.tie(0);
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
cout << BFS(a, b) << '\n';
memset(visited, false,
MAX_N * sizeof(bool)); //매 test마다 visited 초기화
}
}
|
cs |
주요 개념
- 그래프 탐색: 너비 우선 탐색(Breadth-First Search,BFS)
주의 사항
- 매 테스트케이스마다 visited배열을 초기화 시키는것에 유의