BOJ 5014번 스타트링크 ( BFS ) JAVA

BOJ 5014번 스타트링크 ( BFS ) JAVA

---

풀이

BFS를 이용하여 문제를 해결한다. 

 

# DFS로 해결하면 시간 초과 -> 최단 경로는 BFS를 이용해서 구하는 게 효율적임.

# BFS를 사용할 때는 값을 넣음과 동시에 visited를 true로 변경해줘야 한다. ( poll할 때, 넣어주면, 중복이 일어남 )

 

링크

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

 

소스 코드

---

package boj;

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

public class Boj5014 {
    static int s, g, f, u, d;

    public static class Node {
        int stair, cnt;

        public Node(int stair, int cnt) {
            this.stair = stair;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        f = sc.nextInt();
        s = sc.nextInt();
        g = sc.nextInt();
        u = sc.nextInt();
        d = sc.nextInt();
        boolean[] visited = new boolean[f + 1];
        int res = bfs(visited);
        if (res < 0)
            System.out.println("use the stairs");
        else
            System.out.println(res);

    }

    public static int bfs(boolean[] visited) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(s, 0));
        visited[s] = true;
        while (!q.isEmpty()) {
            Node node = q.poll();
            int cur = node.stair;
            if (cur == g)
                return node.cnt;
            if (cur + u <= f && !visited[cur + u]) {
                q.add(new Node(cur + u, node.cnt + 1));
                visited[cur + u] = true;
            }
            if (cur - d >= 1 && !visited[cur - d]) {
                q.add(new Node(cur - d, node.cnt + 1));
                visited[cur - d] = true;
            }
        }
        return -1;

    }
}