백준 5014 스타트링크 Java

Input

1. F: 총 층수, S: 현재 층, G: 목적지, U: 위로 U층, D: 아래로 D층 (1~1,000,000)

Output

1. S -> G 가 가능한, 최소 이동 횟수 / 불가능하면 "use the stairs" 출력

Solve

1. 생각해보면, 한 번 방문한 층수는 다시 갈 필요가 없다는 것을 알 수 있다.
2. 그래서 방문한 곳은 제외하고 이동하면서 count 를 저장하면 된다. (BFS)
3. 현재 층수를 상태로 가지면서 count 배열에 기록한다.
4. 올라가는 경우와 내려가는 경우를 모두 기록하면서 다음 방문지를 계속 큐에 담는다. (1번이 전제되어 있기 때문에 가능)
5. 방문지가 도착지이면 현재 방문지의 count 출력
6. 처음 층수인, S의 위치를 방문 표시 하기 위해 1로 시작 -> 목적지 count 에서 -1 후 출력

Code

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

public class BOJ_5014_스타트링크 {

    private static int F, S, G, U, D;
    private static int[] count;

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

        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());

        count = new int[F + 1];

        System.out.println(bfs());
    }

    private static String bfs() {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(S);
        count[S] = 1;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == G) return String.valueOf(count[cur] - 1);

            int nextUp = cur + U;
            if (nextUp <= F && count[nextUp] == 0) {
                count[nextUp] = count[cur] + 1;
                queue.offer(nextUp);
            }

            int nextDown = cur - D;
            if (nextDown >= 1 && count[nextDown] == 0) {
                count[nextDown] = count[cur] + 1;
                queue.offer(nextDown);
            }
        }

        return "use the stairs";
    }

}