[백준] 1697 숨바꼭질 #JAVA

 

BAEKJOON [1697] 숨바꼭질

---

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException{
		int n,k;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		n = Integer.parseInt(input.split(" ")[0]);
		k = Integer.parseInt(input.split(" ")[1]);
		
		int[] dist = new int[100001];
		
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.add(n);
		
		while (! queue.isEmpty()) {
			
			int temp = queue.poll();
			
			if(temp==k) {
				System.out.println(dist[temp]);
				return;
			}

			//1. 한칸이동 +
			if(temp+1 <100001 && dist[temp+1] == 0){
				queue.add(temp+1);
				dist[temp+1] = dist[temp]+1;
				
			}
			//2. 한칸이동 -
			if(temp-1 >=0 && dist[temp-1] == 0){
				queue.add(temp-1);
				dist[temp-1] = dist[temp]+1;
				
			}
			
			//3. 순간이동 2배이동
			if(2*temp < 100001 && dist[2*temp] == 0){
				queue.add(2*temp);
				dist[2*temp] = dist[temp]+1;
				
			}
				
		}
		
	}

}

 

 

 

 

풀이

---

• BFS
• 수빈이가 움직일 수 있는 거리에 주의한다. 
•  수빈이가 움직이는 거리(?)는 0 ≤ N ≤ 100,000 로 배열을 100,001 의 크기를 갖는다.

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)