[백준] 5014번: 스타트링크

 

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

 

문제 파악

- 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

- 첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

 

<알고리즘 분류>
-그래프 이론
-그래프 탐색
-너비 우선 탐색

 

접근 방법

-최소시간을 구해 리턴해야 하므로 BFS접근을 사용

-정수 배열을 담는 큐 자료형 사용

-정수 배열에는 층x와 버튼을 누른 횟수가 담긴다.

 

 

코드 구현

package com.baekjoon;

public class p5014_스타트링크 {
    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());
        boolean[] visited = new boolean[F+1];
        int cnt=0;
        Queue<int[]> que = new ArrayDeque<>();
        if(S==G){
            System.out.println(0);
            return;
        }
        que.add(new int[]{S,cnt});
        visited[S] = true;
        while(!que.isEmpty()){

            int[] node = que.remove();
            int start = node[0];
            cnt=node[1];

            if(start==G){
                System.out.println(cnt);
                return;
            }

            int[] toGo = new int[]{start+U,start-D};

            for(int x:toGo){
                if(x>=1 && x<=F&&!visited[x]){
                    que.add(new int[]{x,cnt+1});
                    visited[x]=true;
                }
            }
        }


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

 

배우게 된 점

역시나 이 문제는 BFS이지만 

방문 체크를 해줄 때, 중복을 고려해줘야 하는 문제이다.

왔다갔다하면서 중복 분명 생기니 노드를 넣을 때 아예 중복체크를 해서 추가 연산을 줄여주자.

(not visited)

 

그리고 배운 점은

나는 원래 별도 함수를 썼는데 백준 문제의 경우 그냥 메인 함수에 다 쓰고

값을 프린트로 출력해주는 게 나쁘지 않을 것 같다.

(어차피 출력만 해주면 되니까.)

가끔 조건 벗어나면 작업 중지해줘야 할 때 있는데

그럴 때 return; 해주면 됨.

 

마지막에 use the stairs 출력하는 건

그냥 중간에 리턴 안됐으면 마지막에 출력하게끔 하면 된다.

(여기서도 함수를 별도로 썼더라면 리턴값을 별도로 체크해서 출력해줬어야하는데

그거보다 그냥 프린트로 출력하는 게 나은듯)