백준 5014 - 스타트링크

문제

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

리뷰

bfs를 이용하여 풀이할 수 있는 간단한 문제였다.

S 에서 탐색을 시작하여 S+U 나 S-D 중 1~F 까지의 유효한 인덱스 범위안에
존재하며 방문하지 않은 정점으로 탐색을 진행하며 G 에 도달하였을 때 비용을
반환하는 식으로 bfs 로직을 구성하여 풀이했다.
각 정점마다 도달하는데 필요한 비용을 저장하기 위해 Node 클래스를 정의하였다.

풀이하며 유의해야할 점은 층의 범위가 1부터 시작한다는 점이었다.

주어진 문제의 조건에서 정점의 최대 개수가 100만이고 정점마다 가능한 간선의 개수가
최대 2개이므로 로직의 시간복잡도는 $O(2V)$로 수렴한다.
따라서 최대 200만의 연산이 수행될 수 있으므로 문제의 시간 제한인 1초를 무난히
통과한다.

코드

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;


public class Main {
    static int F, S, G, U, D;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        F = parseInt(st.nextToken());
        visited = new boolean[F + 1];

        S = parseInt(st.nextToken());
        G = parseInt(st.nextToken());
        U = parseInt(st.nextToken());
        D = parseInt(st.nextToken());

        int count = bfs(S, G);
        System.out.println(count == -1 ? "use the stairs" : count);
        in.close();
    }

    static int bfs(int start, int end) {
        visited[start] = true;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.floor == end)
                return current.level;

            if (current.floor + U < visited.length && !visited[current.floor + U]) {
                visited[current.floor + U] = true;
                queue.offer(new Node(current.floor + U, current.level + 1));
            }

            if (current.floor - D >= 1 && !visited[current.floor - D]) {
                visited[current.floor - D] = true;
                queue.offer(new Node(current.floor - D, current.level + 1));
            }
        }

        return -1;
    }

    static class Node {
        int floor, level;

        public Node(int floor, int level) {
            this.floor = floor;
            this.level = level;
        }
    }
}

결과