알고리즘/BOJ(C++)

[BOJ] 9019 :: DSLR

쿠마쿠마34 2018. 7. 2. 22:58
반응형

https://www.acmicpc.net/problem/9019


얘도 BFS문제입니다!


앞으로 한동안은 미뤄놨던? 어려운 BFS문제들을 다 풀어서 끝내려고합니당...


이번주 scpc 2차라서 좀 다양한 못접해본 문제들 풀어야 하긴 하는데 ㅠ 몬가 이제와서 새로운 개념 공부해서 풀기 좀 늦은것 같기도하고...


암튼 잡소리 치우고


이문제도 너무 전형적인 bfs문제인데 여기서는 이제 다른 bfs문제랑 다른게 현재 탐색중인 지점이 어디서왔는지를 나타내는것(from배열 이용) 뿐만 아니라 그 지점으로 올때 사용된 방법(how)도 기록을 해주어야 한다는 점 입니다!


 L과 R구하는데 실수만 안하면 하핳...금방 풀수있는 문제입니다

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
#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;
 
bool check[10001];
int from[10001];
char how[10001];
 
int L(int i)
{
    int temp = i % 1000;
    int front = i / 1000;
    int L = temp * 10 + front;
    return L;
}
 
int R(int i)
{
    int last = i % 10;
    int temp = i / 10;
    int R = last * 1000 + temp;
    return R;
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        
        queue<int> q;
        q.push(a);
        check[a] = true;
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
 
            if (now == b)
                break;
            
            if (check[(now * 2) % 10000] == false)
            {
                int next = (now * 2) % 10000;
                q.push(next);
                check[next] = true;
                from[next] = now;
                how[next] = 'D';
            }//D의 경우
            if (now == 0)
            {
                if (check[9999] == false)
                {
                    int next = 9999;
                    q.push(next);
                    check[next] = true;
                    from[next] = now;
                    how[next] = 'S';
                }
            }
            else if (check[now - 1] == false)
            {
                int next = now - 1;
                q.push(next);
                check[next] = true;
                from[next] = now;
                how[next] = 'S';
            }//S인 경우, 0일때 따로 예외처리
        
            int l = L(now);//L연산 결과 만들기
 
            if (check[l] == false)
            {
                int next = l;
                q.push(next);
                check[next] = true;
                from[next] = now;
                how[next] = 'L';
            }
 
            int r = R(now);
            if (check[r] == false)
            {
                int next = r;
                q.push(next);
                check[next] = true;
                from[next] = now;
                how[next] = 'R';
            }
            
 
 
        }
 
        stack<char> s;
 
        while (a != b)
        {
            s.push(how[b]);
            b = from[b];
        }
        
        while (!s.empty())
        {
            cout << s.top();
            s.pop();
        }
        cout << '\n';
 
        for (int i = 0; i <= 10000; i++)
        {
            check[i] = false;
        }
    }
}
cs




반응형