백준 1697 : 숨바꼭질

문제

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

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

입력

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

출력

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

예제 입력 1 복사

5 17

예제 출력 1 복사

4

 

• 풀이

 

최단시간, 최단경로 등이 나오면 bfs를 생각해보자..

첨에 dfs로 하는건가 하고 완전탐색으로 하다가 정답이 안나와서 조건을 추가해보고..

동생좌표랑 현재 좌표에서 이동 가능한 경우의 절대값 비교해서 dfs 하고.. 하는 식으로 잘못짚어서 많이 헤메다가

이전에 풀던 문제들처럼 dist 배열을 만들고 나서 dist를 이전 방문한 노드 + 1로 갱신하는 식으로 bfs로 풀었다

 

그래프 문제를 좀 풀어봤다고 생각했는데 아직 바로바로 생각 안나는걸 보니 더 많이, 다양하게 풀어봐야겠다

import java.util.*;
import java.io.*;

public class Main{

    static int N, M;

    static int maxPos = 100000;

    static boolean[] visit;
    static int[] dist;

    static void bfs(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visit[x] = true;
        dist[x] = 0;

        while (!queue.isEmpty()){
            x = queue.poll();
            int y = x-1;
            if (y >= 0 && y <= maxPos && !visit[y]){
                queue.add(y);
                visit[y] = true;
                dist[y] = dist[x]+1;
            }

            y = x+1;
            if (y >= 0 && y <= maxPos && !visit[y]){
                queue.add(y);
                visit[y] = true;
                dist[y] = dist[x]+1;
            }

            y = x*2;
            if (y >= 0 && y <= maxPos && !visit[y]){
                queue.add(y);
                visit[y] = true;
                dist[y] = dist[x]+1;
            }
        }
    }


    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        visit = new boolean[maxPos+2];
        dist = new int[maxPos+2];
        bfs(N);
        System.out.println(dist[M]);
    }
}