[백준 5014] 스타트링크 (JAVA)

백준 5014번 문제 - 스타트링크

5014번: 스타트링크

---

문제 분석

 

 

• 내 위치(N)와 회사 위치(G)가 주어졌을 때, 앨리베이터를 통해 회사에 갈 수 있는 가장 적은 버튼 수를 출력해라
  • 최대 F층 건물
• 내가 움직일 수 있는 방법(버튼 한번 당)
  • X + U
  • X - D

---

 

해결 키 포인트

 

• 갈 수 있는 방법을 다 했을 때 ! 가장 짧은 시간을 알아내야하므로 모든 방법을 탐색하되 정답에 도착하면 종료해야함
  → BFS 사용
• 처음 위치를 큐에 넣고, 반복하면서 갈 수 있는 방법을 모두 큐에 삽입
• 방문확인을 안할 경우 메모리 초과 발생 → 방문확인 필요 ! (visited)
• 큐에 담겨져 있는 모든 경우의 수를 확인했을 경우 count 증가
  + 마지막에 정답에서 -1 필요 (정답이 나와서 count 증가가 필요 없을 때에서 증가가 발생하므로)

---

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static int F, S, G, U, D;
    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());
        
        int result = BFS();
        if(result == -1)
            System.out.println("use the stairs");
        else
            System.out.println(result);
    }

    static public int BFS() {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean [] visited = new boolean[F+1];

        queue.add(S);
        visited[S] = true;

        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int value = queue.poll();

                // 동생을 찾은 경우
                if (value == G) {
                    visited[G] = true;
                    queue.clear();
                    break;
                }
                // 위로 U층
                if (value + U <= F && !visited[value + U]) {
                    queue.add(value + U);
                    visited[value + U] = true;
                }
                // 아래로 D층
                if (value - D >= 1 && !visited[value - D]) {
                    queue.add(value - D);
                    visited[value - D] = true;
                }

            }
            count++;
        }

        // 회사에 방문했는지 유무
        if(visited[G])
            return count - 1;
        
        return -1;
    }

}