코딩테스트/문제

[백준] 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)

 

주의 사항
  1. 매 테스트케이스마다 visited배열을 초기화 시키는것에 유의