[자바] 백준 1697 - 숨바꼭질

난 BFS로 풀었는데, 사실 DFS가 더 빠를 수 밖에 없을 것 같다. 그리고 넘 쉽게 풀어서 분명 난이도가 높아지는 시리즈 문제들이 있을 거라고 생각했는데, 진짜 있다. 얼핏 봤을 때에는 숨바꼭질 4까지는 N, K 범위도 똑같고 문제도 거의 유사한 것 같은데 난이도가 차이나서 뭐지 싶다. 테스트 데이터 차이인가?

/* 2020.12.12(토)*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().trim().split(" ");
		int N = Integer.parseInt(str[0]);
		int K = Integer.parseInt(str[1]);
		
		boolean[] visited = new boolean[100001];
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(new int[] {N,0});
		
		int cnt = 0;
		int currPos;
		
		int[] tmp;
		int nextPos;
		while(!que.isEmpty()) {
			tmp = que.poll();
			currPos = tmp[0];
			cnt = tmp[1];
			
			//도착한 곳이 동생의 위치면 break;
			if(currPos == K) break;
			
			visited[currPos] = true;
			
			nextPos = currPos * 2;
			if(nextPos>=0 && nextPos<=100000 && !visited[nextPos] ) 
            	que.offer(new int[] {currPos * 2, cnt+1});
			nextPos = currPos +1;
			if(nextPos>=0 && nextPos<=100000 && !visited[nextPos] ) 
            	que.offer(new int[] {currPos + 1, cnt+1});
			nextPos = currPos -1;
			if(nextPos>=0 && nextPos<=100000 && !visited[nextPos] ) 
            	que.offer(new int[] {currPos - 1, cnt+1});
		}		
		System.out.println(cnt);	
	}
}