[백준 13549] 숨바꼭질 3(JAVA)

백준 13549번 문제 - 숨바꼭질 3

13549번: 숨바꼭질 3

---

문제 분석 

 

 

• 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다
• 수빈이는 걷거나 순간이동을 할 수 있다. 
  • 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
  • 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
•  수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 출력해라.

---

해결 포인트

 

• 다익스트라(Dijkstra) 알고리즘 사용
• 최소시간을 알기 위한 Result 클래스 구현
  • 위치 값 n
  • 움직인 시간 count
• Result Comparable는 움직인 시간이 작은 순으로 정렬되도록 구현
• 우선순위 큐 사용
  •  Queue<Result> q = new PriorityQueue<>(); 
• 방문 확인 visited 배열 구현
• 처음 언니 시작 위치 큐에 삽입 
  •  q.add(new Result(N, 0)); 
• 동생 위치에 도착했을 때까지 반복
  
  • 큐에서 하나 꺼내기
  • 방문한 위치면 패스(continue)
  • 방문 안한 위치면 방문 등록 후, 갈 수 있는 공간 큐에 추가
    q.add(new Result(value.n + 1, value.count + 1));
    q.add(new Result(value.n - 1, value.count + 1));
    q.add(new Result(value.n * 2, value.count));
• 동생과 동일한 위치일 경우, value.count 반환 및 출력

---

코드

 

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

public class Main {
    public static int MAX = 100001;

    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());

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

        bw.write(Dijkstra(N, K) + "\n");
        bw.flush();
        bw.close();
    }

    public static int Dijkstra(int N, int K) {
        Queue<Result> q = new PriorityQueue<>();
        boolean[] visited = new boolean[MAX];

        q.add(new Result(N, 0));

        while (!q.isEmpty()) {
            Result value = q.poll();
            if (value.n == K) {
                return value.count;
            }

            if (checkRound(value.n) && !visited[value.n]) {
                visited[value.n] = true;

                q.add(new Result(value.n + 1, value.count + 1));
                q.add(new Result(value.n - 1, value.count + 1));
                q.add(new Result(value.n * 2, value.count));
            }
        }
        return 0;
    }

    public static boolean checkRound(int n) {
        return n >= 0 && n < MAX;
    }

    public static class Result implements Comparable<Result>{
        int n;
        int count;
        public Result(int n, int count) {
            this.n = n;
            this.count = count;
        }

        @Override
        public int compareTo(Result o) {
            if(count == o.count)
                return n - o.n;
            return count - o.count;
        }
    }
}