<Algorithm> 44. 5014번 스타트링크

1. 5014번 스타트링크

• 기본 BFS 문제, 주의할점은 같은 층 일경우 0 , 층수가 100000층까지 가기 때문에 초기 min값을 크게 잡아야 한다.

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 boolean[] visited;
    static int[] dist;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws NumberFormatException, 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());
        visited = new boolean[F+1];
        dist = new int[F+1];
        visited[S] = true;
        dist[S] = 0;
        bfs(F, S, G, U, D);
        
        if(S == G) {
            System.out.println(0);
            return;
        }
        
        if(min != Integer.MAX_VALUE) {
            System.out.println(min);
        }else {
            System.out.println("use the stairs");
        }
    }
    public static void bfs(int F, int S, int G, int U, int D) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(S);
        int[] dx = {U,D};
        
        while(!queue.isEmpty()) {
            int loc = queue.remove();
            
            for(int i = 0 ; i < 2 ; i++) {
                int nloc;
                
                if(i == 0) {
                    nloc = loc + dx[i];
                }else {
                    nloc = loc - dx[i];
                }
                
                if(nloc <= F && nloc > 0 && !visited[nloc]) {
                    visited[nloc] = true;
                    queue.add(nloc);
                    
                    dist[nloc] = dist[loc] + 1;
                    
                    if(nloc == G && dist[nloc] < min) {
                        min = dist[nloc];
                    }
                }
            }
            
        }
        
        
    }
    
}