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

문제

일단 생각하기!

• 수빈이가 이동할 수 있는 좌표는 현재 좌표가 X라면 2*X, X-1, X+1이다. 즉, 한 좌표에서 3개의 좌표로 이동할 수 있다.
• Queue에 int형 배열로 현재 위치와 초를 넣은 뒤 2*X, X-1, X+1을 각각 넣어준다. 이때, 값이 K와 같다면 반복문을 종료한다.
• 이때, 넣었던 값을 체크하지 않는다면 메모리 초과가 나기 때문에 boolean 타입 방문 배열을 만들어 방문 체크를 하며 같은 값은 탐색하지 않도록 한다.

풀이

package BJ;

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

/**
 *
 * [문제] 백준 1697번 숨바꼭질
 * 수빈이는 현재 점 N에 있고, 동생은 점 K에 있을때 수빈이는 2*X, X+1, X-1로 이동할 수 있다.
 * 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하여라.
 * 
 * [아이디어]
 * 수빈이가 이동할 수 있는 것은 2*X, X-1, X+1이므로 처음 시작 좌표에서부터 3개의 좌표로 이동할 수 있다.
 * Queue에 현재 위치와 깊이(=초)를  배열로 넣어 2*X, X-1, X+1을 각각 넣어주며 K에 도달할때까지 찾는다.
 * 이때, 메모리 초과를 방지하기 위해 넣었던 값은 체크를 하여 (그 값으로부터 파생되는 값은 어차피 같기 때문에) 같은 값을 탐색하지 않도록 한다. 
 * 
 * 메모리 : 16,832kb
 * 실행 시간 : 160ms
 * 
 * @author 김유나
 * 2023-08-21
 *
 */

public class BJ_1697_숨바꼭질_김유나 {
	
	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()); // 동생의 위치
		
		int sec = 0; // 동생을 찾을 수 있는 시간
		boolean [] isVisited = new boolean[100001]; // 넣었던 값인지 체크할 배열

		Queue<int []> queue = new ArrayDeque<>();
		queue.offer(new int[] {n, 0}); // 초기값 n(수빈이의 위치), 시간 넣기
		isVisited[n] = true; // n 인덱스 true 체크
		
		while (!queue.isEmpty()) { // queue가 비지 않을 동안
			int current[] = queue.poll(); // 최근의 값
			int loc = current[0]; // 현재 수빈이 위치
			int depth = current[1]; // 깊이(초)
			
			if (loc == k) { // 수빈이가 동생의 위치에 도달했다면
				sec = depth; // 그떄의 깊이가 초가 됨
				break;
			}
			
			depth++; // 깊이 ++
			
			isVisited[loc] = true; // 수빈이 위치의 인덱스 true
		
			// 현재 위치의 2배가 범위 안에 있는지 확인, 이미 넣은 값인지 확인 후 맞다면 queue에 넣고 true 체크
			if (loc * 2 <= 100000 && !isVisited[loc * 2]) {
				queue.offer(new int[] {loc * 2, depth});
				isVisited[loc * 2] = true;
			}
			// 현재 위치의 +1이 범위 안에 있는지 확인, 이미 넣은 값인지 확인 후 맞다면 queue에 넣고 true 체크
			if (loc + 1 <= 100000 && !isVisited[loc + 1]) {
				queue.offer(new int[] {loc + 1, depth});
				isVisited[loc + 1] = true;
			}
			// 현재 위치의 -1이 범위 안에 있는지 확인, 이미 넣은 값인지 확인 후 맞다면 queue에 넣고 true 체크
			if (loc - 1 >= 0 && !isVisited[loc - 1]) {
				queue.offer(new int[] {loc - 1, depth});
				isVisited[loc - 1] = true;
			}
		}
		
		System.out.println(sec); // 시간 출력
	}
}