Baekjoon1697: 숨바꼭질

숨바꼭질

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

133680

37801

23617

25.025%

문제

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

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

입력

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

출력

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

풀이

BFS(큐)를 이용해 풀이할 수 있다.

의문점은 N=501 K=1001일 때 범위 밖으로 벗어나는 경우도 최대 경로에 포함될 수 있다는 점이다.

501 → 1002 → 1001
500 → 1000 → 1001

배열의 크기

위와 같은 케이스에 대비하여 N과 K 값 중 큰 값에 3을 더해 그 값을 배열의 크기로 정한다

int max = Math.max(N,K);
int[] arr = new int[max+3];

BFS

import java.util.*;
public class Main {
	static int[] arr;
	static int N,K,max;
	static int[] move = {-1,1,0};
	public static void bfs(Integer start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		while(!queue.isEmpty()) {
			int now = queue.poll();
			if(now==K){
				break;
			}
			move[2]=now;
			
				for(int i=0;i<3;i++) {
				int next = now + move[i];
				if(next<0 || next> max-1 || arr[next]!=0) {
					continue;
  //경계값을 넘어가면 제외하고, 0이 아닌곳=이미 탐색한 곳이므로 제외
				}
				queue.add(next);
				arr[next]=arr[now]+1;
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		K=sc.nextInt();
		max=Math.max(N, K)+3;
		arr=new int[max];
		arr[N]=1;
		bfs(N);
		System.out.println(arr[K]-1); //초기 위치를 1로 시작했으므로 1을 빼준다
}}