[백준][BOJ-13549][JAVA] 숨바꼭질 3

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

13549번: 숨바꼭질 3

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		Queue<Data> qu = new LinkedList<>();
		boolean[] visited = new boolean[100001];
		qu.add(new Data(N, 0));
		visited[N] = true;
		
		loop:
		while(!qu.isEmpty()) {
			int size = qu.size();
			for(int i=0; i<size; i++) {
				Data data = qu.poll();
				
				if(data.cur == K) {
					System.out.println(data.time);
					break loop;
				}
				
				int left = data.cur-1;
				int right = data.cur+1;
				int time = data.time;
				
				// 순간이동
				if(data.cur >0) teleport(data.cur*2, qu, visited, K, time);
				
				//X-1 or X+1 이동
				if(left>=0 && !visited[left]) {
					qu.offer(new Data(left, time+1));
					visited[left] = true;
				}
				
				if(right <= K && !visited[right]) {
					qu.offer(new Data(right, time+1));
					visited[right] = true;
				}
				
			}
		}
		
	}

	private static void teleport(int i, Queue<Data> qu, boolean[] visited, int K, int time) {
		for(int j=i; j<100001; j*=2) {
			if(visited[j]) continue;
			
			qu.offer(new Data(j, time));
			visited[j] = true;
		}
	}
}

class Data {
	int cur;
	int time;
	public Data(int cur, int time) {
		super();
		this.cur = cur;
		this.time = time;
	}
}

정리

역시 BFS를 이용해서 풀었으며 -1, +1 하는 위치를 구하기 전에 *2인 위치를 먼저 계산했습니다.

단순히 *2인 위치만을 계산한 게 아니라 최대 위치인 100,000까지 전부 계산해둡니다.

그러면 시간이 작은 노드들이 무조건 Queue에 먼저 들어가게 됩니다.