[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 result = bfs(F, S, G, U, D);
        if (result == -1) {
            System.out.println("use the stairs");
        } else {
            System.out.println(result);
        }
    }

    static int bfs(int F, int S, int G, int U, int D) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(S);

        boolean[] visited = new boolean[1 + F];
        visited[S] = true;

        int dist = 0;

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

            while (size-- > 0) {
                int node = q.poll();
                if (node == G) return dist;

                int up = node + U;
                if (up <= F && !visited[up]) {
                    q.offer(up);
                    visited[up] = true;
                }

                int down = node - D;
                if (down >= 1 && !visited[down]) {
                    q.offer(down);
                    visited[down] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

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

int bfs(int f, int s, int g, int u, int d) {
    queue<int> q;
    q.push(s);

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

    int dist = 0;

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

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

            if (node == g) return dist;

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

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

        dist++;
    }

    return -1;
}

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

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

    int res = bfs(f, s, g, u, d);
    if (res == -1) {
        cout << "use the stairs";
    } else {
        cout << res;
    }
}

---