[백준 5014] 스타트링크(Java)

[백준 5014] 스타트링크(Java)

5014번 스타트링크

5014번: 스타트링크

 

해결 방법

1트

처음에 DFS를 이용해서 문제를 해결하려고 했습니다.
G층에 도착했을 때 깊이를 계산하면 되기 때문이죠!

// 시간초과...
private static void dfs(int depth, int now) {

    if(now > f || now <= 0) return;

    // g층에 도착하면
    if(g == now) {
        min = Math.min(min, depth);
        return;
    }

    // 방문 이력이 없으면
    if(!visited[now]) {
        // 방문
        visited[now] = true;
        // u만큼 올라가기
        dfs(depth + 1, now + u);
        // d만큼 내리기
        dfs(depth + 1, now - d);
        // 방문 이력 삭제(모든 노드를 탐색하기 위해)
        visited[now] = false;
    }
}

결과는.. 시간초과!!

 

2트

문제에서 최소한 몇 번의 버튼을 누르는지 구하라고 했으니
BFS를 사용하는 것이 더 좋다는 것을 깨달았습니다.

BFS 가중치가 1일 때 최소 비용을 보장 하기 때문이죠!
(조건이 맞으면 바로 탈출이 가능하기 때문)

풀이

public class Quiz5014 {
    /**
     * F  S G  U D
     * 10 1 10 2 1
     *
     * S 층에서 G층으로 가기위해 눌러야하는 버튼 수의 최솟값
     * U층 위로, D층 아래로
     */

    static int f;
    static int s;
    static int g;
    static int u;
    static int d;
    static boolean[] visited;
    static int min = Integer.MAX_VALUE;

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

        // bfs 수행
        min = bfs(s);
        if(min == - 1) {
            System.out.print("use the stairs");
            br.close();
            return;
        }

        System.out.print(min);
        br.close();
    }

    private static int bfs(int now) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(now, 0));

        while (!queue.isEmpty()) {
            Node poll = queue.poll();

            // 범위 체크
            if(poll.getNode() > f || poll.getNode() <= 0) continue;

            // g층에 도착하면
            if(poll.getNode() == g) {
                return poll.getDepth();
            }

            // 방문 이력이 없으면
            if(!visited[poll.getNode()]) {
                // 방문
                visited[poll.getNode()] = true;
                // u만큼 올라가기
                queue.offer(new Node(poll.getNode() + u, poll.getDepth() + 1));
                // d만큼 내려가기
                queue.offer(new Node(poll.getNode() - d, poll.getDepth() + 1));
            }
        }

        return -1;
    }

    static class Node {
        private int node;
        private int depth;

        public Node(int node, int depth) {
            this.node = node;
            this.depth = depth;
        }

        public int getNode() {
            return node;
        }

        public int getDepth() {
            return depth;
        }
    }
}