백준 스타트링크(5014)

 

오늘은 bfs 문제를 풀었다.

 

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

5014번: 스타트링크

 

어떻게 문제를 처리하는게 좋을까 생각했다 일단 저층부터 고층까지 위아래로 움직이면서 갈수 있는곳 이 있을것이고 도착한곳에 방문기록을 생성하면 나아가면되지않을까 생각했다.

 

방문한곳은 더이상 방문하지않으면서 움직이면 최소한의 이동거리로 방문가능하게 bfs방식으로 움직여줬다.

 

이상하게 81퍼에서 계속 실패를해서 도저히 모르겠다 싶어서 게시판을 봤는데... 

 

0층은 없다.... 0층을 간과해버렸다..

 

0층을 없애니 바로 통과~

 

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

/**
 * https://www.acmicpc.net/problem/5014
 */
public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int 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());

        boolean[] visited = new boolean[F+1];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{S, 0});

        while (!queue.isEmpty()) {

            int[] val = queue.poll();

            int h = val[0];
            int count = val[1];

            if (h == G) {
                System.out.println(count);
                return;
            } else if (visited[h]) continue;

            int up = h + U;
            int down = h - D;
            visited[h] = true;

            if (up >= 0 && up <= F && !visited[up]) {
                queue.add(new int[]{up, count + 1});
            }

            if (down >= 0 && down <= F && !visited[down]) {
                queue.add(new int[]{down, count + 1});
            }
        }

        System.out.println("use the stairs");
    }
}

 

결과