[BOJ] 5014 : 스타트링크

5014 : 스타트링크

풀이

BFS

문제를 간단하게 보고 dfs방법으로 chk배열을 만들어서 중복못하게 한뒤에

조건을 만족하면 up으로 재귀, down으로 재귀 이런식으로 생각없이 짰다.

값이 도착층(G)에 가도 최소인지 확신할 수 없으므로 모든 경우를 탐색해야 한다.

따라서 시간초과를 받았다.

최솟값을 찾을 경우에는 BFS로 풀어야한다.

BFS로 하니까 바로 풀렸다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int chk[1000001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //총 F층 사무실 G층 강호는 S층 ->엘베타고 S층에서 G층으로
    //U는위로 U층, D는 아래로 D층 (두가지 층으로만 움직임, 해당없을경우 안움직임)
    //최소 버튼 횟수
    int f, s, g, u, d;
    int ans = -1;
    cin >> f >> s >> g >> u >> d;
    chk[s] = 1;
    queue<pair<int, int>> q;
    q.push({ s, 0 });
    while (!q.empty()) {
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (x == g) {
            ans = cnt;
            break;
        }
        int there = x + u;
        if (there <= f&&chk[there] == 0) {
            q.push({ there,cnt + 1 });
            chk[there] = 1;
        }
        there = x - d;
        if (there > 0 && chk[there] == 0) {
            q.push({ there, cnt + 1 });
            chk[there] = 1;
        }
    }

    if (ans == -1)
        cout << "use the stairs";
    else
        cout << ans;
    return 0;
}
Written on March 30, 2019