백준 5014번 스타트링크(JAVA) - BFS

백준 5014번

 

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

5014번: 스타트링크

 

문제설명

스타트링크가 있는 건물 층수(F)와 스타트링크의 층수 (G), 현재 위치(S), 해당 층수 만큼 올라가는 버튼(U), 해당 층수 만큼 내려가는 버튼(D)가 주어질 때 S에서 F로 가기위해 눌러야하는 버튼의 최소 횟수를 구하는 문제.

 

 

접근

BFS로 접근

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws 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());

        int[] cnt = new int[1000001];
        Arrays.fill(cnt, Integer.MAX_VALUE);
        cnt[S] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(S);

        while (!q.isEmpty()) {
            int temp = q.poll();

            if (temp == G) {
                System.out.println(cnt[G]);
                return;
            }

            int tx = temp + U;
            if (tx >= 1 && tx <= F && cnt[tx] > cnt[temp] + 1) {
                q.offer(tx);
                cnt[tx] = cnt[temp] + 1;
            }


            tx = temp - D;
            if (tx >= 1 && tx <= F && cnt[tx] > cnt[temp] + 1) {
                q.offer(tx);
                cnt[tx] = cnt[temp] + 1;
            }

        }
        System.out.println("use the stairs");
    }
}

풀이

1. 각 F/S/G/U/D 를 입력 받는다.

2. 최대값인 1000000 만큼 cnt 선언후에 큰 값으로 넣어준다. ( cnt는 해당 층수 까지 가는데 눌린 버튼 횟수)

3. 시작 위치인 S에는 0 으로 수정

4. 큐에 시작위치를 넣고 while문을 돈다.

5. while문 안에서는 맨앞 원소를 뽑은후 도착위치와 같으면 출력후 종료

    -> 그렇지 않다면 현재 층에서 U만큼 더한 값과 D만큼 뺀 값이 층수 범위 내에 존재하는지와 cnt[이동하려는 층] 이 현재 층수 에서 + 1 한 값보다 크다면 해당 값을 큐에넣고 cnt를 수정해준다.

6. while을 하는동안 도착하지 못했다면 마지막에 "use the stairs" 출력