[BOJ] 백준 [5014] 스타트링크 JAVA

문제

 

 

풀이

 

이 문제에서 집어야 할 포인트는 두 가지다.

 

1. BFS를 활용한 우선순위 큐(PQ)를 이용하여 PQ안의 원소를 처리할 때 먼 산으로 가지 않게 하는 것.

 

2. 어느 위치(cur)로 갔을 때, 몇 번 만에 갔는지를 기록하여 (distance[] 배열) 무한 루프로 빠지지 않게 하는 것.

=> 즉 , if(distance[cur+e] > distance[cur]+ 1)   {
                 distance[cur+e] = distance[cur]+ 1;
                 q.add(e + cur);
            }

이 식이 성립해야 하는데, 여기서 cur은 현재위치이고 , e 는 up 또는 down 버튼을 눌렀을 때의 증감치다.

 

 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
 
    static int F; // 총 F층으로 이루어짐
    static int S; // 시작 위치
    static int G; // 목표 위치
    static int U; // 위로 U칸 이동
    static int D; // 아래로 D칸 이동
    static int[] distance;
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        F = Integer.parseInt(input[0]); S = Integer.parseInt(input[1]);G = Integer.parseInt(input[2]);U = Integer.parseInt(input[3]);D = Integer.parseInt(input[4]);
        PriorityQueue<Integer> q = new PriorityQueue<>();
        distance = new int[F+1];
        Arrays.fill(distance,987654321); // distance값 최대로 초기화.
        distance[S] = 0; //첫 시작은 0
 
        q.add(S);
        int[] dir = {U,-D}; // up or down 버튼
        while(!q.isEmpty()){
            int cur = q.poll();
            
            if(cur==G) {
                System.out.println(distance[cur]);
                return;
            }
            for (int e : dir) {
                //범위 벗어나면 탈락.
                if(!isRange(e+cur))
                    continue;
                // 버튼의 수를 최소로 하기위해서 메모이제이션 기법 활용.
                if(distance[cur+e] > distance[cur]+ 1) {
                    distance[cur+e] = distance[cur]+ 1;
                    q.add(e + cur);
                }
            }
        }
        System.out.println("use the stairs");
    }
    static boolean isRange(int pos){
        return pos>=1 && pos <= F;
    }
 
}
 
 

우선순위 큐를 이용한 다익스트라를 아는 사람이면 쉽게 풀 수 있는 문제였다. 끝.