[BOJ] 5014 - 스타트링크

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/5014

5014번: 스타트링크

난이도: 골드 5

사용언어: JAVA

 

풀이

이 문제는 BFS를 사용하여 해결하는 대표적인 유형의 문제입니다. 출발층에서 BFS를 시작하여 스타트링크가 있는 G 층에 도달할 때까지 BFS를 반복해주기만 하면 됩니다. 물론 가장 빨리 도착하는 한 가지 경로만 찾으면 되므로 한 번 도착한 층은 마킹을 해주어 다시 검사하지 않도록 합니다.

 

import java.io.*;
import java.util.*;
 
class Main {
 
    static Queue<Integer> q = new LinkedList<>(); //BFS의 구현을 위한 큐
    static int F, S, G, U, D;
    
    public static void bfs(int x) {
        if (x + U <= F) { // U 칸을 더 올라가도 꼭대기 층을 넘지 않으면
            q.add(x + U); // 큐에 추가
        }
        if (x - D > 0) { // D 칸을 더 내려가도 1층보다 더 내려가지 않으면
            q.add(x - D); // 큐에 추가
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        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());
        int[] arr = new int[F + 1];
        int i, k, n;
        int cnt = 0;
        q.add(S);
        while (!q.isEmpty()) {
            k = q.size();
            for (i = 0; i < k; i++) {
                n = q.poll();
                if (n == G) { // 목표 층에 도착하였다면,
                    bw.write(String.valueOf(cnt) + "\n"); // 버튼을 누른 횟수 출력
                    bw.flush();
                    bw.close();
                    br.close();
                    System.exit(0);
                }
                if (arr[n] != 1) // 이미 검사한 층이 아니라면
                   bfs(n); // bfs 수행
                arr[n] = 1; // 이미 검사한 층은 1로 마킹
            }
            cnt++; // 버튼을 누르는 횟수 카운트
        }
        bw.write("use the stairs\n"); // 만일 갈 수 있는 경로를 찾지 못하였다면
        bw.flush();
        bw.close();
        br.close();
    }
}