[BOJ 1697] 숨바꼭질

JaeungE·2021년 6월 20일

PS

목록 보기

8/22

문제 출처 : [BOJ 1697] 숨바꼭질, https://www.acmicpc.net/problem/1697

👨‍🏫문제

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입/출력

예제 입력
5 17

예제 출력
4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

💻코드

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

public class HideAndSick {
    static int K;

    // 이미 가 본 거리인지 검사하고, 각 단계를 저장해 줄 배열
    static int[] visited;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        K = scan.nextInt();
        visited = new int[100001];

        // 수빈이의 위치를 기준으로 bfs
        search(N);
        
        System.out.println(visited[K] - 1);
        scan.close();
    }

    static void search(int N){
        Queue<Integer> queue = new LinkedList<>();

        // 탐색 도중, 동생에게 도착했는지 알려 줄 변수
        boolean flag = false;
        queue.offer(N);
        visited[N] = 1;

        while(!queue.isEmpty()){
            int poll = queue.poll();

            // bfs시 연걸 노드의 기준은 수빈이가 현재 위치에서 움직일 수 있는 범위다.
            int[] howMove = {poll - 1, poll + 1, poll*2};

            for(int i = 0; i < howMove.length; i++){
                int move = howMove[i];
                
                // 방문한 적이 없고, 범위를 넘지 않는 경우 이동 가능한 거리를 queue에 추가
                if(isBound(move) && (visited[move] == 0)){
                    queue.offer(move);
                    visited[move] = visited[poll] + 1;
                }

                if(move == K){
                    flag = true;
                }
            }

            // 수빈이가 탐색 도중 동생을 만났다면 루프 탈출
            if(flag){
                break;
            }
        }
    }

    // move가 배열 범위를 넘으면 false, 아니면 true를 반환하는 메서드
    static boolean isBound(int move){
        if(move >= 0 && move < visited.length){
            return true;
        }

        return false;
    }
}