[백준 1697] 숨바꼭질 (JAVA)

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

bfs를 이용하여 문제를 해결할 수 있었다.

일차원 배열을 생성하여 index번호에 도달할 수 있는 시간을 저장한다.

따라서 예시에서 수빈이의 위치는 5이고, 동생의 위치는 17이다.

그럼 dp[5]는 0초이다. 그러나 계산하기 쉽게 1로 세팅해준다.

그리고 dp[5-1] , dp[5+1], dp[5*2] 는 1초이다. 계산하기 쉽도록 dp[5]+1을 한다.

만약, 이미 값이 있는 index라면 값을 변경하지 않는다.

 

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

public class Main { 
	static int[] dp = new int[100001];
	static int n, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		bfs(n);
	}

	static void bfs(int n) {
		Queue<Integer> q = new LinkedList<>();
		q.add(n);
		dp[n] = 1;
		while (!q.isEmpty()) {
			int idx = q.poll();
			if(idx==k) {
				System.out.println(dp[idx]-1);
				return;
			}
			if (idx - 1 >= 0 && dp[idx - 1] == 0) {
				dp[idx - 1] = dp[idx] + 1;
				q.add(idx - 1);
			}
			if (idx + 1 <= 100000 && dp[idx + 1] == 0) {
				dp[idx + 1] = dp[idx] + 1;
				q.add(idx + 1);
			}
			if (idx * 2 <= 100000 && dp[idx * 2] == 0) {
				dp[idx * 2] = dp[idx] + 1;
				q.add(idx * 2);
			}
		}
	}
}