스타트링크

📍 문제 설명

 

💡 접근

전형적인 bfs 문제였다. boolean[]으로 방문여부처리해도 되지만 int[]으로 거리기록해서 구해도 된다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k;
    static int[][] board,dis;
    static int[] ch,pm, combi;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int f = kb.nextInt(); //총 층 수
        int s = kb.nextInt(); //시작 층 수
        int g = kb.nextInt(); //가야할 층 수
        int u = kb.nextInt(); //up 버튼
        int d = kb.nextInt(); //down 버튼
        visited = new boolean[f+1];

        //버튼 수의 최솟값이므로 bfs 사용
        solution(f, s, g, u, d);

    }


    static void solution(int f, int s, int g, int u, int d) {
        Queue<Integer> q = new LinkedList<>();
        //현재 층수를 넣기
        q.offer(s);
        //방문 처리
        visited[s] = true;
        //버튼 누른 횟수
        int cnt = 0;
        //도착했나?
        boolean flag = false;

        while (!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                int cf = q.poll();
                if (cf == g) {
                    System.out.println(cnt);
                    flag = true;
                    break;
                }
                //현재 층수에서 갈 수 있는 곳은 가기
                //올라가는 층 수
                int upFloor = cf + u;
                if (upFloor <= f && !visited[upFloor]) {
                    q.offer(upFloor);
                    visited[upFloor] = true;
                }
                //내려가는 층 수
                int downFloor = cf - d;
                if (downFloor > 0 && !visited[downFloor]) {
                    q.offer(downFloor);
                    visited[downFloor] = true;
                }
            }
            cnt++;
        }
        if(!flag) System.out.println("use the stairs");

    }


}