BruteForeceSearch 백준 알고리즘 자바 1697 ‘숨바꼭질’ 문제풀이

Problem

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

Input 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

Output 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

Solution

갈 수 있는 방향이 +1, -1, *2 세 가지이며, 한 번 움직일 때마다 갈 수 있는 방향은 매번 세 가지이다. BFS로 풀어야 한다. (Queue이용)

• 그동안 풀었던 이동 문제와 비슷하게 방향을 나타내는 배열 dir에 현재 위치에서 +1, -1, *2 연산한 값들을 저장한다.
• 다음 스텝이 움직일 수 있는 범위 0이상 100,000이하에 속할 때만 움직인다.
• 방문 확인용 및 그동안 움직인 시간(1초에 한 번 움직이므로 횟수로 생각해도 무방)을 저장하는 visit[] 배열 값이 0이면 (한 번도 해당 지점으로 간 적 없으면) 지금까지 움직인 시간 + 1을 한 값을 저장한다.
• 큐에 넣어준다.
• 큐가 비워지거나, 나의 현재 위치가 동생을 만났다면 (= k) 루프문을 종료한다.
• k에 먼저 도착한 값이 visit[k]에 저장되어 있으므로 (큐는 선입선출) 따로 math.min 연산 없이 visit[k]가 정답이다.

Code

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), k = scan.nextInt(), point = n;
		
		int[] dir = new int[3]; int[] visit = new int[100001];
		Queue<Integer> queue = new LinkedList<>();
		queue.add(n);
		
		while(!queue.isEmpty() && point != k) {
			point = queue.poll();
			dir[0] = point + 1; dir[1] = point - 1; dir[2] = point * 2;
			
			for(int i = 0; i < 3; i++) {
				if(dir[i] >= 0 && dir[i] <= 100000) {
					if(visit[dir[i]] == 0) {
						visit[dir[i]] = visit[point] + 1; queue.add(dir[i]);
					}
				}
			}
		}
		System.out.print(visit[k]);
	}
}