백준 스타트링크 5014 java

문제링크

문제 접근

• 시작 층에서 U만큼 위로, D만큼 아래로 2가지 방향으로 bfs 탐색
• 만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다
• bfs 돌면서 G층 만나면 그 때 카운트 출력 후 종료
• bfs 다 돌게되면 "use the stairs" 출력

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baek_5014 {
    static int F,S,G,U,D;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        F = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        U = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        visit = new boolean[F+1];
        if(S==G) System.out.println(0);
        else bfs();
    }
    private static void bfs(){
        Queue<Integer> que = new LinkedList<>();
        que.add(S);
        visit[S] = true;
        int cnt = 1;
        while(!que.isEmpty()){
            int size = que.size();
            for(int s=0;s<size;s++){
                int now = que.poll();
                int next = now + U; // 위로 U만큼 이동
                if(next <= F && !visit[next]){
                    if(next == G) {
                        System.out.println(cnt);
                        return;
                    }
                    visit[next] = true;
                    que.add(next);
                }
                next = now - D; // 아래로 D만큼 이동
                if(next >= 1 && !visit[next]){
                    if(next == G) {
                        System.out.println(cnt);
                        return;
                    }
                    visit[next] = true;
                    que.add(next);
                }
            }
            cnt++;
        }
        System.out.println("use the stairs"); // G층 못만남
    }
}

결과

정리

• 처음에 놓친 부분이 주어진 입력이 S == G 일 때를 놓침
• 1차원 배열에서 bfs