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

1. 문제

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

5014번: 스타트링크

 

 

2. 풀이 과정

보통 DFS, BFS를 같이 쓸 수 있는 문제가 많아서 대부분 DFS로 풀다가 이번에 오랜만에 BFS 방식으로 풀어서 어색했다. 가능한 경로 중에서 최소 길이를 찾는 문제라서 BFS 방식으로 풀어야 한다.

 

풀이 방식을 간단하게 설명하면, Queue에 방문할 수 있는 층수를 넣고 Queue의 크기만큼 반복문을 돌며 다음 단계에 방문할 수 있는 층을 찾는다. 이미 방문한 층은 다시 방문할 필요가 없으므로 방문체크로 가지치기를 해주었다.

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

public class Main {
    static int F, S, G, U, D;

    public static void main(String[] args) throws Exception {
        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 res = bfs();
        System.out.println((res == -1) ? "use the stairs" : res);
    }

    public static int bfs(){
        int result = -1;
        Queue<Integer> q = new LinkedList();
        boolean[] visited = new boolean[F+1];

        q.add(S);

        while(!q.isEmpty()){
            result++;
            for(int i=0, size = q.size(); i<size; i++){
                int next = q.poll();
                if(next == G){
                    return result;
                }

                int up = next + U;
                if(up <= F && !visited[up]){
                    visited[up] = true;
                    q.add(up);
                }
                int down = next - D;
                if(down > 0 && !visited[down]){
                    visited[down] = true;
                    q.add(down);
                }

            }
        }
        return -1;
    }

}

 

 

결과