[Baekjoon] 백준 5014 스타트링크 (S1 / BFS) - Java

링크

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

5014번: 스타트링크

 

 

 

 

문제 해석

- 입력
첫 번째 줄 : F S G U D
  건물 높이 F층
  현재 위치 S층
  도착할 곳의 위치 G층
  위로 U층을 가는 버튼
  아래로 D층을 가는 버튼


- 출력
if 이동_가능하다면 : 이동가능한 최소값
if 이동_불가능하다면 : use the stairs

 

 

- example 2
100층짜리 건물에서,
내 위치는 S층이며,
2층을 도착해야 하고,
올라가는 것은 1칸씩
내려가는 것은 0칸씩

 

 

 

 

풀이 & 코드 해석

BFS를 사용하면 간단하게 풀 수 있는 문제입니다.

 

이동할 때 누른 버튼 횟수를 구해야 하기 때문에 Queue에 현재 위치를 저장할 때마다 level를 함께 저장하였습니다.

 

 

 

 

코드

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

public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 첫 번째 줄
        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());


        bfs(F, S, G, U, D);


    }

    static class Point {
        int now;
        int level;

        Point(int now, int level) {
            this.now = now;
            this.level = level;
        }
    }

    static void bfs(int F, int S, int G, int U, int D) {

        boolean[] floor = new boolean[F + 1];
        floor[0] = true;

        Queue<Point> q = new LinkedList<>();

        q.offer(new Point(S, 0));

        while (!q.isEmpty()) {
            Point p = q.poll();

            if (p.now == G) {
                System.out.println(p.level);
                return;
            }

            if (p.now + U <= F && floor[p.now + U] == false) {
                floor[p.now + U] = true;
                q.offer(new Point(p.now + U, p.level + 1));
            }

            if (p.now - D >= 1 && floor[p.now - D] == false) {
                floor[p.now - D] = true;
                q.offer(new Point(p.now - D, p.level + 1));
            }
        }

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

    }


}

 

 

 

 

발생한 문제 & 해결 방안

-

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java