[JAVA/BFS] 백준 5014 스타트링크

1. 문제

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

5014번: 스타트링크

 

2. 풀이

BFS로 풀이했다

(1) n층을 최소한의 버튼을 눌러 도착했을 때의 버튼 누른 횟수를 저장하는 배열(minBtn)을 사용해 정답을 구하고, 중복을 체크하는데 사용한다.

(2) 위의 최소 버튼 누른 횟수를 저장하는 배열(minBtn)에서 시작점의 버튼 누른 횟수를 0이 아닌 1로 처리해, 시작점과 처음 도착한 층의 차이점을 만들어 처리한다.

(3) 맨 마지막 정답을 처리할때, +1 한 값을 빼준다.

 

3. 코드

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.io.*;

public class Main {
        
    // bfs를 사용해 버튼 누르는 횟수를 계산
    public static String getCnt(int F, int S, int G, int U, int D){
        Queue<Integer> q = new LinkedList<Integer>();
        int[] minBtn = new int[F+1]; // n층에 도착하기 위해 눌러야할 버튼의 최소 횟수
        Arrays.fill(minBtn, 0); // 도착하지 않음 처리
        
        q.add(S);
        minBtn[S] = 1; // 첫번째 층 중복 방문 막기 위해
            
        while(!q.isEmpty()){
            int now = q.poll();
            
            // 도착
            if(now == G) {
                return String.valueOf(minBtn[now] - 1); // 처음에 더한 1 값 빼줌
            }
            
            if(now + U <= F && minBtn[now + U] == 0) {
                minBtn[now + U] = minBtn[now] + 1;
                q.add(now + U);
            }
            if(now - D >= 1 && minBtn[now - D] == 0) {
                minBtn[now - D] = minBtn[now] + 1;
                q.add(now - D);
            }
        }
            
        return "use the stairs";
    }
        
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int F = Integer.parseInt(input[0]);
        int S = Integer.parseInt(input[1]);
        int G = Integer.parseInt(input[2]);
        int U = Integer.parseInt(input[3]);
        int D = Integer.parseInt(input[4]);
            
        System.out.println(getCnt(F, S, G, U, D));
    }
}