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

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

 

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

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

---

1.  아이디어

 

BFS 알고리즘을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

현재 위치 S에서 G까지 가야하는데 위로 U, 아래로 D만큼 이동하는 상황의 반복으로 G를 가야한다. 이는 S를 시작으로 현재위치 C에 대해 C + U, C - D 위치가 다음 위치가 되고 다시 다음 위치에서 +U, -D를 반복하는 상황으로 최단 거리를 구하는 BFS와 동일한 로직이다. 이를 활용해 다음 위치가 건물 내 위치면서 방문한 적이 없으면 방문하는 BFS로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    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());

        int dist = bfs(F, S, G, U, D);
        if (dist == -1) System.out.println("use the stairs");
        else System.out.println(dist);
    }

    private static int bfs(int F, int S, int G, int U, int D) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(S);

        boolean[] visited = new boolean[1 + F];
        visited[S] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int node = q.poll();
                if (node == G) return dist;

                int upstairs = node + U;
                if (upstairs <= F && !visited[upstairs]) {
                    q.offer(upstairs);
                    visited[upstairs] = true;
                }

                int downstairs = node - D;
                if (downstairs >= 1 && !visited[downstairs]) {
                    q.offer(downstairs);
                    visited[downstairs] = true;
                }
            }

            dist++;
        }

        return -1;
    }

}

---

4. 후기