[BAEKJOON 백준] 1697 숨바꼭질

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는 정수이다.

 

먼저 K의 최대값인 100000에 1을 더해 boolean 배열을 만들어 줍니다. 그리고 시작점을 입력을 받아 queue를 만들어 넣어줍니다. 시작점 위치를 true로 해주고, BFS를 시작합니다.

 

수빈이는 두가지의 행동중 하나를 1초마다 행동할 수 있다. 하나는 걷기, 하나는 순간이동 이다. 그래서 두가지의 경우를 if를 통해 나누어 준다.

각 각의 경우가 발생할 조건을 만족했을때, visit 배열에서 false 일경우만 조건을 만족하게 하고, 해당하는 조건을 만족해서 실행할때, visit 배열은 true로 바꾸어 다시 방문하는 일이 없도록 한다.

이렇게 작성을 하면 모든 점을 탐색하게 되고, 만약에 이미 방문한 적이 있는 곳인 경우는 더 적은 수로 방문했을 경우기 때문에, 더이상 방문하지 않고 queue에 들어가지 않게 된다.

 

그렇게 방문하게 되면 동생의 위치에 도달하게 되면 그때 while문은 끝이 나고, 그동안 세어준 count를 출력하게 된다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine()," ");
		
		Scanner sc=new Scanner(System.in);
		int A=Integer.parseInt(st.nextToken());
		int B=Integer.parseInt(st.nextToken());
		boolean visit[]=new boolean[100001];
		LinkedList<Integer>que=new LinkedList<>();
		que.offer(A);
		visit[A]=true;


		int count=0;
		outer:
		while(!que.isEmpty()) {
			int size=que.size();
			for(int i=0;i<size;i++) {
				int temp=que.poll();
				if(temp==B)break outer;
				if(temp>0&&!visit[temp-1]) {
					que.offer(temp-1);
					visit[temp-1]=true;
					
				}
				if(temp<100000&&!visit[temp+1]) {
					
					que.offer(temp+1);
					visit[temp+1]=true;
					
				}
				if(temp*2<100001&&!visit[temp*2]){
					que.offer(temp*2);
					visit[temp*2]=true;
					
				}
			}
			count++;
			
		}
		System.out.println(count);
	}

}