백준 13549 java - 숨바꼭질 3(BFS)

문제, 입출력, 테스트케이스

2트만에 성공!

50분 중에서 6분 36초를 남겨두고 성공!

단순한 BFS라고 생각하면 틀리는 문제이다. 조건이 필요한 BFS 문제이다.

 

<문제 접근/풀이과정>
1. 0 <= 수빈 <= 100,000, 0 <= 동생 <= 100,000 -> 100,001크기를 가진 int 배열 필요함(커봐야 대충 100,000만큼의 시간 걸림)
2. 걷기 = X-1, X+1 -> 1초 / 순간이동 2*X-> 0초 
3. 동생이 수빈이 보다 작은 수에 있다면 무조건 걸어야 함
4. bfs를 돌리되 순간이동을 써서 간 경우가 걷기로 간 경우보다 시간이 적게 들면 순간이동으로 이동한 시간으로 갱신
5. 순간이동 했을 때 2배가 되므로 100,000보다 크지 않은 것인지 체크, -1만큼 갔을 때 0보다 작은 지 체크가 필요

 

<소스 코드>

package boj;

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

public class Boj_13549 {
	static int arr[];
	static int N, K;

	public static void main(String[] args) {
		// 0 <= 수빈 <= 100,000, 0 <= 동생 <= 100,000
		// 걷기 = X-1, X+1 -> 1초 / 순간이동 2*X-> 0초
		// 동생보다 수빈이가 너 낮은 수의 점에 있을 땐 순간이동을 사용

		Scanner sc = new Scanner(System.in);
		arr = new int[100001]; // 0부터 100,000까지
		N = sc.nextInt();
		K = sc.nextInt();
		Arrays.fill(arr, -1);
		if (N >= K) {
			System.out.println(N - K);
		} else {
			bfs();
			System.out.println(arr[K]); 
		}
	}

	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.add(N);
		arr[N] = 0;
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			if(cur == K) {
				return;
			}
			
			int teleport = cur*2;
			int walkBackward = cur-1;
			int walkForward = cur+1;
			
			
			if(teleport <= 100000 && arr[teleport] < arr[cur] ) {
				arr[teleport] = arr[cur];
				q.add(teleport);
			}
			
			if(0 <= walkBackward && arr[walkBackward] == -1) {
				arr[walkBackward] = arr[cur] + 1;
				q.add(walkBackward);
			}
			if(walkForward <= 100000 &&arr[walkForward] == -1) {
				arr[walkForward] = arr[cur] + 1;
				q.add(walkForward);
			}
		}
	}
}