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

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

1697번: 숨바꼭질

• 풀이

기준점에서 +1, -1, *2 된 점까지 가는 시간은 1초이다. 그래프의 인접 노드라고 생각할 수 있는 것이다. 따라서 BFS를 이용하여 1초 걸리는 지점을 방문 → 또 그 지점을 기준으로 1초 걸리는 지점을 방문을 반복하다 보면 각 점까지 도달하는 최소 시간을 찾아낼 수 있다. 동생의 위치인 K에 도달하면 반복을 멈추고 걸린 시간을 출력한다.

• 코드

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

public class Main {
	static int N, K; // 수빈이와 동생의 위치
	static int time[]; // 소요 시간
	static int move [] = new int []{1, -1, 2};
	
	static void find() {
		Queue<Integer> que = new ArrayDeque<>();
		
		que.add(N);
		if (N==K) return; // 수빈이와 동생의 위치가 같다면 종료
		
		while(!que.isEmpty()) {
			int now = que.poll(); // 기준점
			
			for (int i=0; i<3; i++) {
				int next;
				if (i==2) next = now * move[i]; // 순간이동
				else next = now + move[i]; // 걷기
				
				if (next<0 || next>100_000 || time[next]!=0) continue; // 범위 내에 있고, 아직 방문하지 않았다면
				time[next] = time[now]+1; // 소요 시간 저장
				que.add(next); // 큐에 삽입
				if (next == K) return; // 동생 찾으면 종료
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		time = new int[100_001];
		
		find();
		System.out.println(time[K]);
	}

}