티스토리 뷰

#출처 : https://www.acmicpc.net/problem/5014




처음엔 DFS 로 풀다가 메모리초과 떠서 DP까지 생각해 내기 전에 BFS로 다시 풀었다.

BFS를 쓸 때 check 배열의 필요성을 못느껴서 dist배열 하나로 끝냈다.




#풀이 

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
#include <iostream>
#include <queue>
#define endl '\n'
#define MAX 1000005
using namespace std;
int F, S, G, U, D;
int dist[MAX];
 
bool inRange(int x)
{
    return x >= 1 && x <= F;
}
void BFS(queue<int>& q)
{
    while (q.size())
    {
        int pos = q.front();
        q.pop();
 
        int nextU = pos + U;
        if (inRange(nextU) && !dist[nextU])
        {
            dist[nextU] = dist[pos] + 1;
            q.push(nextU);
        }
 
        int nextD = pos - D;
        if (inRange(nextD) && !dist[nextD])
        {
            dist[nextD] = dist[pos] + 1;
            q.push(nextD);
        }
    }
    if (dist[G])
        cout << dist[G] - 1 << endl;
    else
        cout << "use the stairs" << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> F >> S >> G >> U >> D;
    queue<int> Q;
    Q.push(S);
    dist[S] = 1;
    BFS(Q);
    return 0;
}
cs


댓글
댓글쓰기 폼
공지사항
Total
290,627
Today
19
Yesterday
32
링크
TAG
more
«   2022/08   »
  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      
글 보관함