[BaekJoon] 5014번 - 스타트링크 [Java][C++]

문제 링크

---

1. 아이디어

최단 거리 BFS를 활용하면 해결할 수 있는 문제로 S층부터 U층 위로 가거나 D층 아래로 가는 과정을 반복하면 된다. 이때 건물의 최소 높이보다 낮은 층이나 최대 높이보다 높은 층을 가지 않도록 주의해야 한다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int f = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int g = Integer.parseInt(st.nextToken());
        int u = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        int dist = bfs(f, s, g, u, d);
        if (dist == -1) {
            System.out.println("use the stairs");
        } else {
            System.out.println(dist);
        }
    }

    static int bfs(int f, int s, int g, int u, int d) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(s);

        boolean[] vis = new boolean[1 + f];
        vis[s] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int sz = q.size();

            while (sz-- > 0) {
                int cur = q.poll();
                if (cur == g) return dist;

                int up = cur + u;
                if (up <= f && !vis[up]) {
                    q.offer(up);
                    vis[up] = true;
                }

                int down = cur - d;
                if (down >= 1 && !vis[down]) {
                    q.offer(down);
                    vis[down] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int f, s, g, u, d;

int bfs() {
    queue<int> q;
    q.push(s);

    vector<bool> vis(1 + f);
    vis[s] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            int cur = q.front();
            q.pop();

            if (cur == g) return dist;

            int up = cur + u;
            if (up <= f && !vis[up]) {
                q.push(up);
                vis[up] = true;
            }

            int down = cur - d;
            if (down >= 1 && !vis[down]) {
                q.push(down);
                vis[down] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> f >> s >> g >> u >> d;

    int dist = bfs();
    if (dist == -1) {
        cout << "use the stairs";
    } else {
        cout << dist;
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---