백준 5014번 스타트링크 (JAVA)

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

5014번: 스타트링크

 

전형적인 DFS & BFS 문제이다.

이 문제에서 먼저 생각난 풀이 방식이 BFS 여서, BFS 방식으로 풀이했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;
import org.w3c.dom.Node;

public class Main {

    static Function<String, Integer> stoi = Integer::parseInt;
    static int F, S, G, U, D;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        F = stoi.apply(st.nextToken());
        S = stoi.apply(st.nextToken());
        G = stoi.apply(st.nextToken());
        U = stoi.apply(st.nextToken());
        D = stoi.apply(st.nextToken());
        int ans = bfs();
        System.out.println(ans == -1 ? "use the stairs" : ans);
    }

    private static int bfs() {
        boolean[] visit = new boolean[F + 1];
        visit[S] = true;
        Queue<Node> que = new ArrayDeque<>();
        que.add(new Node(S, 0));

        while (!que.isEmpty()) {
            Node now = que.poll();
            if (now.floor == G) {
                return now.cnt;
            }
            if (now.floor + U <= F && !visit[now.floor + U]) {
                visit[now.floor + U] = true;
                que.add(new Node(now.floor + U, now.cnt + 1));
            }
            if (now.floor - D > 0 && !visit[now.floor - D]) {
                visit[now.floor - D] = true;
                que.add(new Node(now.floor - D, now.cnt + 1));
            }
        }
        return -1;
    }

    static class Node {

        int floor;
        int cnt;

        Node(int floor, int cnt) {
            this.floor = floor;
            this.cnt = cnt;
        }
    }
}