[JAVA] # 13549 숨바꼭질 3

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

13549번: 숨바꼭질 3

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

public class Main{

    static int N, K;
    static int[] board = new int[200001];
    static boolean[] visited = new boolean[200001];

    /*
        주의사항
        - 순간이동을 하는게 시간상 더 유리하다
     */
    public static void bfs(int idx) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(idx);
        visited[idx] = true;
        while(!queue.isEmpty()) {
            int e = queue.poll();
            if(e == K) {
                System.out.println(board[K]);
                System.exit(0);
            }
            if(e * 2 <= 100000 && !visited[e * 2]) { // 순간이동 케이스를 최우선으로 큐에 넣는다
                for(int i = e * 2; i <= 100000 && !visited[i]; i *= 2) { // "e의 배수" 아님!!
                    visited[i] = true;
                    board[i] = board[e];
                    queue.add(i);
                }
            }
            if(e - 1 >= 0 && !visited[e - 1]) {
                visited[e - 1] = true;
                board[e - 1] = board[e] + 1;
                queue.add(e - 1);
            }
            if(e + 1 <= 100000 && !visited[e + 1]) {
                visited[e + 1] = true;
                board[e + 1] = board[e] + 1;
                queue.add(e + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        bfs(N);
    }
}

BFS..? 로 풀었다.

 

저번 숨바꼭질 문제랑 다른점이 있다면 

X - 1 과 X + 1으로 이동하는 경우는 시간이 1초 걸리지만

2 * X로 순간이동하는 경우는 시간이 0초 걸린다는 점이다!!

 

그래서 순간이동을 할 수 있는 x * 2 케이스들을 큐에 제일 먼저 넣어놓고 다 방문한 다음에

그 이후에 x - 1과 x + 1점들을 처리하는 식으로 풀어보니 해결 되었다!

 

 

그리고 쪼금 조심해야 할게 x * 2라고 하면 4, 8, 16, 32 .... 순이다

괜히 처음에 4, 8, 12, 16 이렇게 4의 배수로 이동한다고 생각해서 풀어서 약간 해맸었다.

 

질문게시판도 조금 뒤져봤는데

위와같은 가중치가 존재하는 간선에서의 최단거리를 찾고자 할때는 "다익스트라 알고리즘"을 사용하는 것이 정석적인 풀이라고 한다.

 

그럼 해결!