[백준 ]5014: 스타트링크 - JAVA

문제

www.acmicpc.net/problem/5014

5014번: 스타트링크

풀이

S -> G로 가는 최단 경로를 찾는 문제이므로 BFS를 사용하여 풀었다. 

 

이미 방문한 층을 다시 방문하면 최단 경로가 아니기 때문에 visited를 사용하여 다시 방문하는 일이 없도록 하였다. 또한 노드 class를 만들어 현재 층의 위치와 현재까지 몇번의 버튼을 눌렀는지 기억하도록 하였다. 

 

이 문제에서 주의할 점이 있는데 예제 입력 1번을 잘 이해했다면 넘어가도 된다.

예를 들어, 예제 1번에서 1 -> 10으로 가는 방법 중 버튼을 최소로 누르는 방법이고 이때 만일 현재 층보다 높은 층으로 갈 때는 up버튼만 누르도록 구현을 했다면 use the stairs가 출력될 것이다.

 

즉, 항상 up버튼, down버튼을 함께 눌러주어서 최단 경로를 찾아주어야 한다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int f, s, g, u, d;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        f = scan.nextInt();
        s = scan.nextInt();
        g = scan.nextInt();
        u = scan.nextInt();
        d = scan.nextInt();
 
        visited = new boolean[f + 1];
        int result = bfs();
        
        if(result < 0) System.out.println("use the stairs");
        else System.out.println(result);
    }
 
    public static int bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(s, 0));
        visited[s] = true;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(current.x == g) return current.cost;
            
            if(current.x + u <= f && visited[current.x + u] == false) {
                q.offer(new Node(current.x + u, current.cost + 1));
                visited[current.x + u] = true;
            }
            if(current.x - d >= 1 && visited[current.x - d] == false) {
                q.offer(new Node(current.x - d, current.cost + 1));
                visited[current.x - d] = true;
            }
        }
        return -1;
    }
    
    public static class Node {
        int x;
        int cost;
        
        public Node(int x, int cost) {
            this.x = x;
            this.cost = cost;
        }
    }
}