숨바꼭질


백준 1697: 숨바꼭질

문제보기
Alt text

풀이

BFS를 이용
답 출력시, 수빈이 위치 이동 시간을 1부터 시작 했기 때문에 -1 한 후 출력함을 주의

소스코드

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	//수빈이의 위치
		int K = sc.nextInt();	//동생의 위치
		Queue<Integer> queue = new LinkedList<>();	//수빈이의 위치를 담을 큐
		int visit[] = new int[100001];	//칸의 이동여부를 알기위해 + 각 칸에 도착한 시간을 담을 것
		int min = Integer.MAX_VALUE;
		
		queue.add(N);
		visit[N] = 1;
		
		while(!queue.isEmpty()) {
			N = queue.poll();
			
			if(N == K) {	//도착
				if(visit[N] < min)
					min = visit[N];
			}
			if(N+1 <= 100000 && visit[N+1]==0) {
				queue.add(N+1);
				visit[N+1] = visit[N]+1;
			}
			if(N-1 >= 0 && visit[N-1]==0) {
				queue.add(N-1);
				visit[N-1] = visit[N]+1;
			}
			if(N*2 <= 100000 && visit[N*2]==0) {
				queue.add(N*2);
				visit[N*2] = visit[N]+1;
			}
		}
		
		System.out.println(min-1);
	}
}