[백준 Baekjoon] 5014번 스타트링크 - JAVA

백준 Baekjoon 5014번 스타트링크 - JAVA

---

문제 풀이

위, 아래 버튼 두개를 잘 조합하여 원하는 층으로 최단거리로 이동하는 문제이다. 이런식으로 최단거리를 구할때에는 BFS탐색을 사용하여 쉽게 풀 수 있다. 층의 수가 1000000까지 밖에 안되고 위, 아래 두가지만 있어 큐에 위로 갔을 경우 아래로 갔을 경우 두 가지 모두 추가해주고, 도착하면 이동 횟수를 출력함으로서 쉽게 구할 수 있다. 제한사항이 크지 않아도 위, 아래의 조합에서 중복이 많이 발생 할 수 있어 boolean 배열로 체크를 해줘야 한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

        if (D == 0 && S > G) {
            System.out.println("use the stairs");
            return;
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[] visit = new boolean[F + 1];

        queue.add(new int[]{S, 0});
        visit[S] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            if (cur[0] == G) {
                System.out.println(cur[1]);
                return;
            }

            if (cur[0] + U <= F && !visit[cur[0] + U]) {
                queue.add(new int[]{cur[0] + U, cur[1] + 1});
                visit[cur[0] + U] = true;
            }

            if (cur[0] - D > 0 && !visit[cur[0] - D]) {
                queue.add(new int[]{cur[0] - D, cur[1] + 1});
                visit[cur[0] - D] = true;
            }
        }

        System.out.println("use the stairs");
    }
}