[백준_5014]_스타트 링크

Link

문제

현재 위치 시점으로 부터 목표 지점까지 가는데 최소 이동횟수를 구하는 문제이다.
※엘리베이터의 up은 몇층씩 가고 down 몇층씩 가는지이다.

그래프적으로 생각하면 각 층수를 정점으로 생각하고 간선의 가중치는 모두 1이다. 그 대신 각 층수는 인접한 층끼리만 연결되있다.

예제 입력 1번의 예:
10 1 10 2 1

현재 층 :1
목표 층 :10
up : 2칸씩 건너 뛸 수 있다.
down : 1칸식 건너 뛸 수 있다.

알고리즘 원리

---2----2-----2----2-----2----(-1)
1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 10

up 5번 down 1번으로 목표 층수에 도달 할 수 있다.

package Thur_Sunday_aWeek_Al.SW_MaestroReady;

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

public class startLink {
    static int F,S,G,U,D;
    static int dist[];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        F=sc.nextInt(); // total
         S=sc.nextInt(); // current
         G=sc.nextInt(); // object
         U=sc.nextInt();
         D=sc.nextInt();
         dist=new int[F+1];
        int ans=bfs();
        if(ans==-1)
        {
            System.out.println("use the stairs");
        }
        else
            System.out.println(ans-1);

    }
    static int bfs()
    {
        Queue<Integer> q=new LinkedList<>();
        dist[S]=1; // 현재 점을 1로 초기화
        q.offer(S);
        while (!q.isEmpty())
        {
            int cur=q.poll();
            if(cur==G)
            {// 목표지점 도착하면 종료. (가장 먼저 도착한 거다)
                return dist[cur];
            }
            int up=cur+U;
            int down=cur-D;
            if(up>0 && up<=F && dist[up]==0)
            {
                dist[up]=dist[cur]+1;
                q.offer(up);
            }
            if(down>0 && down<=F && dist[down]==0)
            {
                dist[down]=dist[cur]+1;
                q.offer(down);
            }
        }
        return -1;
    }

}