[Algorithm] 백준 5014(BOJ 5014) 스타트링크 문제풀이!! (Java)

---

안녕하세요 coding-knowjam입니다.

오늘은 백준 온라인 저지에 있는 5014번 스타트 링크 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

해당 문제는 내가 현재 있는 층(S)에서 목표로 하는 층(G)으로 이동하기 위해 엘리베이터를 몇 번을 이용해야 하는지를 출력해야 하는 문제입니다.

사실문제가 S, G, U, D 이런 문자들을 서서 읽기가 조금 불편할 뿐이지 BFS를 통해서 아주 쉽게 풀 수 있습니다.

간단한 풀이이므로 글로 설명을 해보자면 다음과 같습니다.

1. 현재 있는 층에서 엘리베이터를 이용해 이동할 수 있는 2가지의 경우를 모두 구합니다.
2. 이동한 층을 모두 방문 처리합니다. (1번에서 2가지의 경우로 이동했으니 2개의 경우 모두 방문처리)
3. 이동한 층을 현재층이라고 가정하고 1번과 동일하게 이동 가능한 2가지의 경우를 모두 구합니다.
4. 이때, 앞에서 방문 처리된 경우는 탐색을 멈추고 제외하며, 방문하지 않은 층만 이동하고 방문 처리합니다.
5. 3~4를 반복하면서 해당 층에 도달하면 이동한 횟수(BFS 수행된 횟수)를 출력합니다.

전체 층의 개수가 백만 개이므로 BFS를 통한 완전 탐색을 하더라도, 방문 처리한 부분은 걸러지므로 시간 복잡도 측면에서도 통과가 충분히 가능합니다.

그럼 코드로 살펴보겠습니다.

 

2. Java로 문제 풀이

package algorithm.boj;

import java.util.*;

public class BOJ_5014 {
    private static Scanner scanner = new Scanner(System.in);
    private static int numberOfTotalFloor;
    private static int currentFloor;
    private static int destinationFloor;
    private static List<Integer> upDownValues;
    private static int[] visitedFloor;

    public static void main(String[] args) {
        // 문제에서 주어진 데이터 입력 받기
        Integer[] inputData = readLineAndChangeIntegerArray(" ");
        numberOfTotalFloor = inputData[0];  // 전체 층의 개수
        currentFloor = inputData[1];        // 현재 내가 있는 층
        destinationFloor = inputData[2];    // 내가 이동해야 하는 층(스타트링크)
        upDownValues = List.of(inputData[3], -inputData[4]);     // 엘리베이터로 이동할 수 있는 층의 개수(up, down)를 배열로 저장

        // 현재 있는 층이 스타트링크면 0(이동 횟수) 출력
        if (currentFloor == destinationFloor) {
            System.out.println(0);
            return;
        }

        // BFS를 위한 큐
        Queue<Integer> queue = new LinkedList<>();
        // 방문처리를 저장할 배열 (1:방문, 0:미방문)
        visitedFloor = new int[numberOfTotalFloor + 1];
        // 현재 층을 큐에 담고 방문처리
        queue.offer(currentFloor);
        visitedFloor[currentFloor] = 1;
        // 엘리베이터 타고 이동한 횟수(BFS 횟수)
        int countOfMove = 0;

        // 순회 시작
        while (!queue.isEmpty()) {
            // 동일하게 이동한 거리에서 방문할 수 있는 층의 개수만큼만 반복(level 순회하기 위함) 
            int numberOfRepeat = queue.size();
            for (int i = 0; i < numberOfRepeat; i++) {
                Integer floor = queue.poll();   // 현재 층

                for (int j = 0; j < upDownValues.size(); j++) {
                    int nextFloor = floor + upDownValues.get(j);
                    // 현재 층에서 엘리베이터 타고 이동가능(전체 층을 벗어날 수 없음)하면서 방문하지 않은 층인가?
                    if (isPossibleToMove(nextFloor)) {
                        // 목표 층에 도달했으면 현재까지 이동한 횟수+1 출력
                        if (destinationFloor == nextFloor) {
                            System.out.println(countOfMove + 1);
                            return;
                        }
                        // 아니라면 다음 level 순회를 위해 큐에 넣고 방문처리
                        queue.offer(nextFloor);
                        visitedFloor[nextFloor] = 1;
                    }
                }
            }
            // 동일한 이동거리에서 방문가능한 층(동일 level)을 모두 순회하면 이동한 횟수 1 증가
            countOfMove++;
        }
        // BFS 순회가 종료되면 이동 불가능하므로 문구 출력
        System.out.println("use the stairs");
    }

    /**
     * 이동 가능한 층인지 확인
     * @param nextFloor : 다음에 이동할 층
     */
    private static boolean isPossibleToMove(int nextFloor) {
        return nextFloor <= numberOfTotalFloor && nextFloor >= 1 && visitedFloor[nextFloor] == 0;
    }

    /**
     * 문자열 1줄을 읽어서 정수형 배열로 변환
     * @param delimiter : 문자열을 자르기 위한 구분자
     */
    private static Integer[] readLineAndChangeIntegerArray(String delimiter) {
        return Arrays.stream(scanner.nextLine().split(" "))
                .map(Integer::valueOf)
                .toArray(Integer[]::new);
    }
}

주석과 코드를 같이 살펴보시면 이해하는데 크게 어렵지 않으실 겁니다.

감사합니다.

---