[Java] 백준 1697번 : 숨바꼭질

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

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-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

[풀이 과정]

수빈이의 위치에서 가장빠른시간 안에 동생이 있는 좌표로 찾아가면 되는 문제이다.

 

1. x+1 

2. x-1

3. x*2

 

1초마다 3가지 방법 중 하나로 갈 수 있다.  너비 우선 탐색으로 각각의 좌표로 갈 수 있는 최단거리를 구하면서 동생의위치에 왔을 때 정답을 출력하면 된다.

 

1) 범위가 ( 0 ≤ N,K ≤ 100,000) 이기때문에 크기가 100,001 배열을 만든다. 수빈의 인덱스(위치)의 값을 1로 변경한다.

-수빈의 위치를 큐에 넣어준다.

 

2) 수빈과 동생의 좌표를 가지고 너비우선 탐색을 한다. 

 

- 큐에 들어있는 좌표값을 꺼낸다. 큐에서 꺼낸 좌표값을 기준으로 이동할  좌표값이 0보다 작으면 안되고 배열의 크기보다 크면 안된다.

-방문하지않은 좌표값 (arr[다음위치]==0) 일때만  x+1 / x-1 / x*2 의 위치에 대해서 다시 큐에 집어 넣는다.

- 최단 거리를 구해주기 위하여 arr[다음좌표] = arr[현재좌표] +1 을 하여 거리 계산을 누적한다.

-큐가 비어있을때까지 반복한다.

 

3 ) 현재좌표가 동생좌표가 같다면 정답을 출력한다.

 

 [코드]

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

public class Main {
    static int size=100001;
    static  int[] arr = new int[size];
    static  Queue<Integer> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        arr[N]=1; //수빈 위치
        queue.add(N);//수빈 위치 넣기
        bfs(N,K); //수빈 위치에서 너비 우선 탐색

    }
    static void bfs  (int start,int end){

       while (!queue.isEmpty()){

           int now = queue.poll();

           if(now==end){ //동생 위치를 찾았다면 출력하고 return한다.
               System.out.println(arr[end]-1);
               return;
          }

       
           if(now -1 != -1 && arr[now-1]==0){ // -1
               queue.add(now-1);
               arr[now-1]=arr[now]+1;
           }

           if(now +1 < size &&arr[now+1]==0){ // +1
               queue.add(now+1);
               arr[now+1]=arr[now]+1;
           }

            if (now*2 <size &&arr[now*2]==0){ // *2
               queue.add(now*2);
               arr[now*2]=arr[now]+1;
           }


       }

    }
}

 

[결과]