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

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제

해결 방안

time 배열의 index는 해당 위치이고 값은 해당 위치를 수빈이가 최소 몇 초를 나타낸다.
또한 수빈이는 3가지 방법으로 이동할 수 있으므로 3가지 방법으로 이동한 위치의 값이 k 일때까지 너비우선 탐색을 해주면 된다.

코드

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

// 숨바꼭질
// 수빈이 N 동생 K
// 수빈이는 걷거나 순간이동 가능
public class Main {

	static int n;
	static int k;
	static int[] time;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		n = Integer.parseInt(str.split(" ")[0]);
		k = Integer.parseInt(str.split(" ")[1]);

		time = new int[100001];
		
		if(n==k)
			System.out.println(0);
		else
			bfs();
	}
	
	static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.offer(n);
		
		int current = 0;
		
		int next = 0;
		while(!q.isEmpty()) {
			current = q.poll();

			for(int i=0; i<3; i++) {
				if(i==0) {
					next = current+1;
				}
				else if(i==1) {
					next = current-1;
				}
				else {
					next = 2*current;
				}
				
				if(next == k) {
					System.out.println(time[current]+1);
					return;
				}
				
				if(next>=0 && next<=100000 && time[next]==0) {
					q.offer(next);
					time[next] = time[current]+1;
				}
				
			}
		}
	}

}