백준 5014 스타트링크(JAVA)

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

5014번: 스타트링크

 

 

 

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_5014_스타트링크 {
    static int f;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        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());
        int ans = -1;

        boolean[] building = new boolean[f+1];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {s, 0});
        building[s] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[0] == g){
                ans = cur[1];
                break;
            }

            if(check(cur[0]+u) && !building[cur[0]+u]){
                q.add(new int[] {cur[0]+u, cur[1]+1});
                building[cur[0]+u] = true;
            }

            if(check(cur[0]-d) && !building[cur[0]-d]){
                q.add(new int[] {cur[0]-d, cur[1]+1});
                building[cur[0]-d] = true;
            }
        }

        if(ans == -1)
            System.out.println("use the stairs");
        else
            System.out.println(ans);
    }//main
    private static boolean check(int x){
        if(x<=0 || x>f)
            return false;
        return true;
    }
}

이거와 유사한 문제가 많았던 것 같은데, 풀어보길 바란다.

층을 방문했는지 안했는지 boolean 배열을 이용해서 작성하고, bfs를 이용해서 방문 체크를 한다.

이때, u,d를 이용해서 다음 층을 계산하는데, 범위를 넘어가는 것은 큐에 삽입되지 못하도록 check 함수를 만들었다.

그리고 한 칸 씩 넘어갈때마다 방문 횟수를 저장해두면 된다!!

 

마지막으로, 만약 방문 횟수가 처음에 지정한 -1이라면, 목표 층에 도달하지 못했다는 것이므로 계단을 이용하면 된다.

만약 -1이 아니라면 목표 층에 도달한 것이므로 그 값을 출력하면 끝!