[백준] 5014 스타트링크 (JAVA)

✉️문제

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

5014번: 스타트링크

 

📝 접근

   먼저 문제를 예제를 통해 이해해보자. [ 10, 1, 10, 2, 1 ] 의 입력이 들어왔을 때 이는 다음과 같다. 

 -> 건물은 10층으로 구성되어 있고 강호는 현재 1층에 있다. 스타링크까지 가야하는데 현재 스타링크의 위치는 10층에 있으며, 올라갈 때는 2층씩 올라갈 수 있고 내려갈 때는 1층씩 내려갈 수 있다. 이 때의 최단 거리를 구하는 문제이다. 필자는 최단 거리를 구할 때는 보통 BFS를 이용하는 편이다.

 

🗝 문제풀이

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class B5014 {

    static int[] dis = new int[1000001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int F = sc.nextInt(); // F층까지 있음
        int S = sc.nextInt(); // 강호의 위치
        int G = sc.nextInt(); // 스타 링크의 위치
        int U = sc.nextInt(); // 위로 가는 버튼
        int D = sc.nextInt(); // 아래로 가는 버튼

        BFS(F, S, G, U, D);

        int answer = dis[G] - 1; // 방문 체크를 위해서 1부터 시작했기 때문에 -1을 해야 한다.
        if(answer == -1) System.out.println("use the stairs"); 
        else System.out.println(answer);
    }

    public static void BFS(int f, int s, int g, int u, int d) {
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        dis[s] = 1;
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                int cur = q.poll();
                if(s == g) return;
                int nu = cur + u;
                int nd = cur - d;

		// 올라갈 때는 건물의 최대 높이인 f까지
                if(nu <= f && dis[nu] == 0) {
                    q.add(nu);
                    dis[nu] = dis[cur] + 1;
                }

		// 내려갈 때는 건물의 최소 높이인 1까지
                if(nd >= 1 && dis[nd] == 0) {
                    q.add(nd);
                    dis[nd] = dis[cur] + 1;
                }
            }
        }
    }

}

 

// ==================================== 
// 다음의 코드를 배열에 담아서 리팩토링하면 코드가 조금 간결해질 수 있다.
if(nu <= f && dis[nu] == 0) {
    q.add(nu);
    dis[nu] = dis[cur] + 1;
}

if(nd >= 1 && dis[nd] == 0) {
    q.add(nd);
    dis[nd] = dis[cur] + 1;
}