백준 No.13549 숨바꼭질 3 - JAVA

문제

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

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

 

 

 

디버깅을 통한 풀이

첫 시작은 Node(수빈의 위치, 시간은 0) 으로 먼저 queue에 담는다. 

 

첫 if문은 수빈이가 현재 있는 위치가 동생의 위치와 같은 경우 작은 값을 넣는 것인데 이떄 처음 들어가는 값이 바로 min변수에 값이 할당되어야 하므로 min은 Integer.MAX_VALUE로 초기화시킨다.

그러고 나서 계속 반복되는데 이떄 문제에서 주어진 2 * X, X+1, X-1 중에 동생의 위치에 도달한 값들이 여러가지가 있을 것이고 그 중 가장 작은 값이 출력되어야 해서 Math.min으로 묶는다.

 

이렇게 총 3개의 if문이 만들어지게된다. (문제에서 이동하는 방법이 3가지라서)

이게 만약 현재 위치에서 주어진 범위를 탈출하면 안 되기 때문에 now.v * 2 <= max 처리를 해야하고,

해당 노드가 당연히 방문이 안 되어있어야만 하기 방문이 가능해서 방문을 안 했는지도 체크한다. 방문을 안 했을 경우에 queue에 해당 노드를 담는다. 근데 여기서 이동을 하면 시간이 걸리게 되고 해당 시간은 순간이동시 0 , 한칸 이동시 1이다.

그래서 new Node하면서 타임도 값을 변경해주어야 한다.

while문이 처음 반복할 때는 전부 반복한 적이 없는 노드들이기에 바로 queue에 담긴다.

 

if( 5*2 <= 100,000 && !visited[5*2]) queue.add(new Node(5*2, 0));

if( 5+1 <= 100,000 && !visited[5+1]) queue.add(new Node(5+1, 0));

if( 5-1 >= 0 && !visited[5-1]) queue.add(new Node(5-1, 0));

이런식으로 진행된다. 이게 계속 queue(우선순위 큐)에 담아지고 빠지고를 반복하면서 방문하지 않은 곳에 방문하고 시간을 계속 추가해나가면서 값이 동생의 위치에 도달하게 된다면 일단 min에 넣는다. queue에 아직 값이 남았다면 더 반복하면서 동생의 위치에 도달할 수 있는 방법을 찾는다. 그러다 도달할 경우 값을 Math.min을 통해 더 작은 값을 min에 넣고 출력한다.

 

 

처음 한 바퀴를 돌면서 3가지 값을 queue에 담고 다시 돈다. 이떄 time값으로 정렬이 되므로 time이 제일 작은 순간이동 먼저 확인한다.

현재 위치가 10일 경우 세가지 경우를 모두 queue에 담는다.

그러면 기존에 있던 2개 +  현재 위치 10일 경우 3걔 해서 총 5개가 queue에 존재하게 된다. 

근데 이렇게 풀어보고 생각해보니... 우선순위 큐(time정렬)일 경우 순간 순간이동으로 할 경우 time이 0이기 때문에 순간이동을 다 돌고나서 진행하게 된다... 그래도 정답이긴 하다. 이럴 경우 queue를 사용하는 것도 좋은 거 같은데 결과를 출력해보니 queue를 사용했을 때가 더 시간이 오래걸린다... 선입선출이라 어짜피 순간이동을 도는 건 마찬가지였다.

아무튼 그래서 이렇게 돌고 돌아 순간이동일 경우를 먼저 다 털어내고  그 다음에 한칸 이동한 값들을 하나씩 확인해나간다. 그렇게 엄청 많은 값들을 탐색해나가다 결국 겹치는 값들 중에서 제일 작은 값을 찾아 출려한다.

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int n;   //수빈
    static int s;   //동생

    static boolean visited[];
    static int max = 100000; //주어지는 최대값

    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        s = sc.nextInt();

        visited = new boolean[max+1];

        djs();

        System.out.println(min);
    }

    static void djs(){
        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> o1.time - o2.time));
        queue.add(new Node(n,0));   //수빈의 위치에서 시작함

        while (!queue.isEmpty()){

             Node now = queue.poll();
            visited[now.v] = true;
             if(now.v == s) min = Math.min(min, now.time);

             if(now.v * 2 <= max && !visited[now.v * 2]) queue.add(new Node(now.v * 2, now.time));
             if(now.v + 1 <= max && !visited[now.v + 1]) queue.add(new Node(now.v + 1, now.time+1));
             if(now.v - 1 >= 0 && !visited[now.v - 1]) queue.add(new Node(now.v - 1, now.time + 1));
        }
    }

    static class Node{
        int v;
        int time;

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

 

참고
https://moonsbeen.tistory.com/97

[백준]13549: 숨바꼭질 3 - JAVA