[BOJ] 백준 5014 - 스타트링크 풀이

1. 문제

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

5014번: 스타트링크

 

2. 풀이

백준 실버 1에 해당하는 문제이다. BFS를 너무 오랜만에 풀어서 그런지 쉬운 문제인데도 감을 잡는데 오래 걸렸다..(복습의 중요성..)

입력으로 주어지는 값을 저장한 후 BFS 함수를 실행한다.
BFS 함수에서는 먼저 큐를 선언하고 현재 위치를 저장한다. (37줄)
그 후 큐가 비어있을 때까지 while 반복문을 돌면서 현재 큐의 사이즈만큼 for 반복문을 돈다. for 반복문 안에서는 먼저 큐의 값을 꺼내서 이 값이 내가 현재 도달해야하는 목표 위치인지를 확인하고 맞다면 flag를 true로 두고 반복문을 빠져 나온다. 아니라면 U만큼 더하고, D만큼 뺀 값이 범위안에 있는 수이거나 내가 방문한 층이 아닐 경우 큐에 더한다. 이렇게 하면 모든 경우의 수를 구하면서 최솟값을 구할 수 있다.

while 반복문 마지막에 flag 변수를 확인하여 참이라면 1를 리턴 후 지금까지 반복문을 돈 횟수(result)를 출력한다.(67줄, 26줄)
만약 주어진 입력으로 현재층에서 목표층까지 도달할 수 없다면 -1를 리턴 후 "use the stairs"를 출력한다.(72줄, 28줄)

 

3. 소스 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int F, S, G, U, D;
    static int result = 0;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());

        visited = new boolean[1000001];

        int flagInt = startLinkBFS();
        if (flagInt == 1) {
            bw.write(Integer.toString(result));
        } else {
            bw.write("use the stairs");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int startLinkBFS() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(S);
        boolean flag = false;

        while (!queue.isEmpty()) {
            int size = queue.size();
            int location = 0;

            for (int i = 0; i < size; i++) {
                location = queue.poll();

                if (location == G) {
                    flag = true;
                    break;
                }

                int loU = location + U;
                int loD = location - D;

                if (loU <= F && !visited[loU]) {
                    visited[loU] = true;
                    queue.add(loU);
                }
                if (loD > 0 && !visited[loD]) {
                    visited[loD] = true;
                    queue.add(loD);
                }
            }

            if (flag) {
                return 1;
            }
            result++;
        }

        return -1;
    }
}