[백준 1697번] 숨바꼭질 - JAVA

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

1697번: 숨바꼭질

풀이

사용한 알고리즘 : 다익스트라

 

풀이전략

우선순위큐를 이용한 다익스트라 알고리즘을 통해 문제를 해결했다.

 

먼저 특정 위치로 이동했을 때 이동한 횟수를 알기위해

특정 위치와 해당 위치까지의 이동횟수를 저장하는 클래스를 선언한다.

 

문제에서 최소 이동횟수로 목적지에 도착하는 것이 목표이기 때문에

이동횟수를 우선순위 비교대상으로 삼고, 이를 Comparable 인터페이스를 사용해 오름차순으로

우선순위 큐에 저장되도록 구현한다.

 

그리고 다익스트라 알고리즘의 BFS 탐색 중, 목표로 하는 지점에 도착하면

Comparable 인터페이스 구현으로 인한 최소 이동거리로 목적지에 도착한 것이므로

해당 인덱스에서의 이동거리를 출력하면 정답이 도출된다.

 

제출코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Node implements Comparable<Node>{
        int index;
        int cost;

        public Node(int index, int cost){
            this.index=index;
            this.cost=cost;
        }

        @Override
        public int compareTo(Node o) {
            if(this.cost<o.cost) return -1;
            else return 1;
        }
    }

    static int N,K;
    static int result=0;
    static boolean visited[];

    static void dijkstar(Node startNode){
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(startNode);

        while(!q.isEmpty()){
            Node now = q.poll();

            if(now.index==K){
                result=now.cost;
                break;
            }

            if(visited[now.index]) continue;
            visited[now.index]=true;

            if(now.index-1>=0) q.offer(new Node(now.index-1,now.cost+1));
            if(now.index+1<200001) q.offer(new Node(now.index+1,now.cost+1));
            if(now.index*2<200001) q.offer(new Node(now.index*2,now.cost+1));
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        visited = new boolean[200001];
        Node startNode = new Node(N,0);
        dijkstar(startNode);

        bw.write(result+"\n");
        bw.flush();
        bw.close();
    }
}