[JAVA] 백준 알고리즘 5014번 (스타트링크)

문제

---

이번에 다뤄볼 문제는 5014번 문제 '스타트링크'입니다.

스타트링크 문제에서 연습해야 하는 key-point는 BFS입니다.

 

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

 

따라서 해당 문제를 풀기 위해 앞으로 탐색을 시작할 층을 담을 queue를 하나 만들고 방문한 층을 기록할  visited 배열을 하나 만듭니다.

 

visited에 담기는 값이 곧 방문 횟수가 되는데요.

예를들면

4층에서 시작할 경우 visited[4]의 값은 1부터 시작합니다. (한번에 방문했다는 의미죠?)

그리고 엘리베이터가 위로 2층, 아래로 2층 움직이는 조건을 받았다고 가정하면

visited[6]과 visited[2]는 각각 0으로 탐색한 적 없는 층이기 때문에

이번 루프에 방문하도록 합니다. 따라서 방문 수치도 +1이 되어야 하겠죠?

visited[6], visited[2]에는 각각 2라는 값을 줍니다. (2 = visited[4] + 1)

이제 6층과 2층에서 탐색을 시작하면 되기 때문에 큐에 담아주고 다음 루프로 넘어갑니다.

 

이런 과정을 반복하면 무난하게 해결 할 수 있겠습니다.

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    // 스타트링크
    public static void main(String[] args) {
        // F: 전체층, S: 강호 위치, G: 목적지
        // U: 위로 이동 수, D: 아래로 이동 수
        Scanner sc = new Scanner(System.in);
        int f = sc.nextInt();
        int s = sc.nextInt();
        int g = sc.nextInt();
        int u = sc.nextInt();
        int d = sc.nextInt();

        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[f + 1];
        q.add(s);
        visited[s] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();
            if (now == g) {
                System.out.println(visited[now] - 1);
                break;
            }
            if (now + u <= f && visited[now + u] == 0) {
                visited[now + u] = visited[now] + 1;
                q.add(now + u);
            }
            if (now - d >= 1 && visited[now - d] == 0) {
                visited[now - d] = visited[now] + 1;
                q.add(now - d);
            }
        }

        if (visited[g] == 0) {
            System.out.println("use the stairs");
        }
    }
}

 

5014번: 스타트링크