숨바꼭질
백준 1697: 숨바꼭질
풀이
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);
}
}