[Java] BOJ1697_숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

동생의 위치는 고정되어 있고 수빈이는 1초에 뒤쪽으로 한 칸씩만 갈 수 있으므로 N >= K 일 때 결과는 N-K이다.

 

그 외 경우에는 BFS를 통해 탐색을 해야한다. 현재 위치를 n이라 할 때 n-1, n+1, n * 2의 위치에 대해 경곗값 체크와 방문 체크를 통해 Queue에 추가해야 한다. 이때 이동시간인 cnt를 같이 담고 다닌다.

 

n == K일때 가장 최소 시간으로 동생을 만난 것이기 때문에 함수를 빠져나온다.

 

import java.io.*;
import java.util.*;

public class Main {

	static int N, K;
	static int res = 0;
	static boolean[] visit;
	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());
		visit = new boolean[100001];
		if(N > K) {
			System.out.println(N-K);
			return;
		} else if(N == K) {
			System.out.println(0);
			return;
		} else {
			bfs();
		}
		
		System.out.println(res);
	}

	public static void bfs() {
		Queue<int[]> q = new LinkedList<int[]>();
		
		q.offer(new int[] {N, 0});
		visit[N] = true;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int n = temp[0];
			int cnt = temp[1];
			if(n == K) {
				res = cnt;
				return;
			}
			if(n-1 >= 0 && !visit[n-1]) {
				q.offer(new int[] {n-1, cnt+1});
				visit[n-1] = true;
			}				
			if(n+1 <= 100000 && !visit[n+1]) {
				q.offer(new int[] {n+1, cnt+1});
				visit[n+1] = true;
			}				
			if(2*n <= 100000 && !visit[n*2]) {
				q.offer(new int[] {n*2, cnt+1});
				visit[n*2] = true;
			}
		}
	}
}