5014 스타트링크

BOJ::5014 스타트링크

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

bfs를 이용하여 목적지에 가장 빠르게 도착하는 경우를 찾으면 된다.

1차원배열로 방문여부 체크가 가능하지만, 버튼을 '몇 번' 눌러야 하는지 알아야 하므로

Node 클래스를 만들어 현재위치, 몇번째인지를 같이 확인했다.

<JAVA>

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 Main {
    
    static int F,S,G,U,D;
    static boolean visited[]=new boolean[1000001];
    
    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());
        
        bfs(S);
    }
    
    public static void bfs(int a){
        visited[a]=true;
        Queue<Node> q = new LinkedList();
        q.add(new Node(a,0));
        int dx[]={U,-D};
        while(!q.isEmpty()){
            int cur = q.peek().cur; //현재위치
            int time = q.poll().time; //몇 번째 버튼을 눌렀는지
            
            if(cur==G){
                System.out.println(time);
                return;
            }
            
            for(int i = 0 ; i < 2 ; i++){
                int next = cur+dx[i]; // 다음 위치
                if(next>0 && next<=F){
                    if(!visited[next]){
                        visited[next]=true;
                        q.add(new Node(next,time+1));
                    }
                }
            }
        }
        //목적지에 도달 할 수 없는 경우
        System.out.println("use the stairs");
    }
}
class Node{
    int cur;
    int time;
    Node(int c, int t){
        cur=c;
        time =t;
    }
}