[백준] 13549 숨바꼭질3

 

 

문제 출저

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

13549번: 숨바꼭질 3

 

 

문제 풀이

수빈이의 위치에서 동생까지 가는 시간을 구하는게 이 문제의 목표이다.

수빈이는 1초 후에 현재 위치에서 +1, -1 가거나 0초 후에 현재 위치*2인 위치로 이동할 수 있다.

 

범위는 0, 100000이므로 십만개의 칸을 가진 int 배열을 생성하고 해당 위치에 몇 초 후에 도착하는지를 저장한다.

BFS로 시작 위치 n을 시작으로 탐색을 진행하며 0초 후에 *2인 위치로 갈 수 있기 때문에 탐색한 위치의 기존에 저장되어 있는 시간과 현재 시간을 비교하여 작은 것을 우선으로 저장하는 로직을 추가하였다. 

 

 

소스 코드

package baekjoon;

/*
숨바꼭질3
https://www.acmicpc.net/problem/13549


 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B13549 {

    static int n;
    static int k;
    static int[] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        board = new int[100001];
        Arrays.fill(board, -1);

        Queue<dot> que = new LinkedList<>();
        que.add(new dot(n, 0));
        int count = 0;
        board[n] = 0;
        while (!que.isEmpty()) {
            dot d = que.poll();

            int plus = d.location + 1;
            int minus = d.location - 1;
            int teleport = d.location * 2;

            if(teleport <= 100000 && (board[teleport] == -1 || board[teleport] > d.count)) {
                board[teleport] = d.count ;
                que.add(new dot(teleport, d.count));
            }

            if(plus <= 100000 && (board[plus] == -1 || board[plus] > d.count+1) ) {
                board[plus] = d.count+1;
                que.add(new dot(plus, d.count + 1));
            }
            if(minus >= 0 && (board[minus] == -1 || board[minus] > d.count+1)) {
                board[minus] = d.count+1;
                que.add(new dot(minus, d.count + 1));
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(board[k]);
        System.out.println(sb);

    }

    public static class dot {
        int location;
        int count;

        dot(int location, int count) {
            this.location = location;
            this.count = count;
        }
    }


}