백준 13549 - 숨바꼭질 3

문제

13549번: 숨바꼭질 3

정답률이 낮아서 좀 쫄았는데 생각보다 다익스트라 기본 문제 느낌...??

---

조건

• 수빈이의 위치 N, 동생의 위치 K ( 0 ≤ N,K ≤ 100,000)
• 수빈이는 3가지의 이동 방법을 가지고 있다.
  • 현재 위치 X일 때 → (X-1) , (X+1), (2*X)
  • (X-1) , (X+1) 은 이동하는데 1초 걸림
  • (2*X)은 순간이동이라 0초 걸림

---

접근법

1. 간선의 비용(가중치)이 1인 경우와 0인 경우 두 가지
2. 입력으로 탐색 시작 지점이 주어진다.

→ 위의 두 경우를 만족하는 최적의 알고리즘 = 다익스트라 알고리즘

다익스트라 알고리즘을 이용해서 시작 지점부터 이어지는 모든 지점의 최소 비용을 갱신

---

문제 풀이 - 우선순위 큐

public class p13549 {

		
    public static boolean[] visited;

	//시작지점으로부터의 최소 비용을 저장하는 배열
    public static int[] dist;

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

        visited = new boolean[100001];
        dist = new int[100001];
        
        Arrays.fill(dist, Integer.MAX_VALUE);

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        dijkstra(start);

        System.out.println(dist[end]);

    }

    public static void dijkstra(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.second - o2.second;
            }
        });

        queue.add(new Node(start, 0));
        dist[start] = 0;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            visited[now.v] = true;

            for (int i = 0; i < 3; i++) {
                Node next = new Node();

                if (i == 0) {
                    next.v = now.v - 1;
                    next.second = 1;
                }
                if (i == 1) {
                    next.v = now.v + 1;
                    next.second = 1;
                }
                if (i == 2) {
                    next.v = now.v * 2;
                    next.second = 0;
                }

                if (next.v < 0 || next.v > 100000) {
                    continue;
                }

                if (!visited[next.v] && dist[next.v] > dist[now.v] + next.second) {
                    dist[next.v] = dist[now.v] + next.second;
                    queue.add(new Node(next.v, dist[next.v]));
                }
            }
        }

    }

    public static class Node {
        int v;
        int second;

        public Node(int v, int second) {
            this.v = v;
            this.second = second;
        }

        public Node() {
        }
    }
}