백준5014_스타트링크

import java.util.Scanner;
 
public class Main {
 
    static boolean visit[] = new boolean[1000001];
    static int depth[] = new int[1000001];
    static boolean able = true;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        int F = sc.nextInt(); // 총 층수
        int S = sc.nextInt(); // 시작층수
        int G = sc.nextInt(); // 도착층수
        int U = sc.nextInt();
        int D = sc.nextInt();
 
        Q queue = new Q();
        queue.Push(S);
        depth[S] = 0;
        visit[S] = true;
        BFS(queue, U, D, F, G);
         
         
        if(depth[G] == 0 && S!=G)
            System.out.println("use the stairs");
        else
            System.out.println(depth[G]);
    }
 
    public static void BFS(Q queue, int U, int D, int F, int G) {
 
        while (queue.getCount() != 0) {
            int v = queue.Pop();
 
            if (v + U <= F && v + U >= 1) {
                if (!visit[v + U]) {
                    queue.Push(v + U);
                    depth[v + U] = depth[v] + 1;
                    visit[v+U] = true;
                }
            }
            if (v - D >= 1 && v - D <= F) {
                if (!visit[v - D]) {
                    queue.Push(v - D);
                    depth[v - D] = depth[v] + 1;
                    visit[v-D] = true;
                }
            }
        }
    }
}
 
class Q {
 
    int q[] = new int[1000001];
    int s = 0;
    int e = 0;
 
    public void Push(int x) {
        q[e] = x;
        e++;
    }
 
    public int Pop() {
 
        if (e == 0)
            return -1;
 
        int pop = q[s];
        for (int i = 1; i < e; i++) {
            q[i - 1] = q[i];
        }
        q[e - 1] = 0;
        e--;
        return pop;
    }
 
    public int getCount() {
        return e;
    }
 
}

[알고리즘]

큐로 먼저 풀었다. 사실 큐로 안풀고도 더 쉽게 풀수있을 것 같아서 그대로 풀어보려 했는데...!

뭘 잘못 생각한건지 자꾸 시간초과가 났다. 결국 조건 몇개의 위치라던지 좀 자잘하게 생각못해준 부분이 있어서 그랬던 것 같다. 

그래서 이웃님의 코드를 참고해 고쳐봤는데 ( 근데, 참고하다 보니 완전 똑같아짐 )

그래서 그냥 큐로 푼 것으로 올렸다 ㅋㅋㅋ

경로를 따라서 depth 값을 누적시키고, 마지막 도착점의 depth 값을 출력해주는 것이다.

그 층이 방문되지 않았다면, queue에 포함해주고, 지금 층의 depth 값을 더해준다. 결국 경로를 따라가면서 depth 값이 누적된다.

아마도 최소 뎁스값보다 더 높은 층도 있겠지만, 어쨌든 BFS로 다 돌고 난 후 목표층의 depth 값을 추출하면 되니 상관은 없다...