BOJ 5014 스타트링크 [Java]

BOJ 5014 스타트링크

1. 문제 링크

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

2. 문제 해설

bfs를 이용하여 최단 거리를 묻는 문제는 유명한 유형이다. 이 문제에서 버튼의 최솟값은 결국 최단 거리의 다른 표현이다.
한가지 내가 처음에 실수하였던 부분은 이동할 수 있는 칸 수를 나타내는 배열을 {u, -d}로 하지 않고 {u, d}로 하였던 것이다.
이 점 빼고는 무난한 bfs 구현이다.

3. 코드 보기

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int f, s, g, u, d;
    static int ans;
    static int[] dis;
    static int[] button;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        f = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        g = Integer.parseInt(st.nextToken());
        u = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        ans = -1;
        dis = new int[f + 1];
        button = new int[]{u, -d};
 
        Arrays.fill(dis, -1);
        BFS(s);
 
        if (ans == -1) {
            sb.append("use the stairs");
        } else {
            sb.append(ans);
        }
 
        bw.write((sb.toString()));
        br.close();
        bw.flush();
        bw.close();
    }
 
    static void BFS(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dis[start] = 0;
 
        while (!q.isEmpty()) {
            int cur = q.poll();
 
            if (cur == g) {
                ans = dis[cur];
                return;
            }
 
            for (int i = 0; i < 2; i++) {
                int nxt = cur + button[i];
 
                if (nxt > f || nxt < 1 || dis[nxt] >= 0) {
                    continue;
                }
 
                q.add(nxt);
                dis[nxt] = dis[cur] + 1;
            }
        }
    }
}