13549 - 숨바꼭질 3[G5]

 

문제

 

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

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

 

풀이

 

풀이의 핵심은 PQ 사용을 통한 '가장 짧은 시간'을 항시 탐색하는 것.

3가지의 조건 분기를 PQ에 던지기만 한다면 heap을 통해 최단 거리를 항상 판정할 수 있다.

 

또한 중복 처리 방지를 위해 visited를 사용하고 큐에서 빠졌을 때 방문 처리를 하는 것. (이전에 처리해서 에러가 났었다.)

 

 

코드

import java.util.*;
import java.io.*;
class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); //수빈이 위치
        int k = Integer.parseInt(st.nextToken()); //목표

        //메모리 초과 해결 위함 : 중복된 좌표를 동일 반복 가능하기에 체크 표시 필요
        boolean[] visited = new boolean[100000 + 1];

        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.add(new Pos(n, 0)); //현재 수빈이 위치 기준



        while (!pq.isEmpty()) {
            Pos now = pq.poll();
            if(visited[now.x]) continue;
            visited[now.x] = true;

            if(now.x == k) { //목표 달성
                System.out.println(now.time);
                return;
            }

            if(now.x > 0 && !visited[now.x - 1]) {
                pq.add(new Pos(now.x - 1, now.time + 1));
            }
            if(now.x < 100000 && !visited[now.x + 1]) {
                pq.add(new Pos(now.x + 1, now.time + 1));
            }
            if(now.x * 2 <= 100000 && now.x > 0 && !visited[now.x * 2]) {
                pq.add(new Pos(now.x * 2, now.time));
            }
        }

    }
}
class Pos implements Comparable<Pos> {
    int x; //위치
    int time; //걸린 시간

    public Pos(int x, int time) {
        this.x = x;
        this.time = time;
    }

    @Override
    public int compareTo(Pos p) {
        return Integer.compare(this.time, p.time); //시간 적은 순서대로
    }
}