백준 1697 숨바꼭질 Java

정해진 배열에서 찾는 문제만 풀다가 애매한 문제라고 생각이 들어서 코드를 짜는데 시간이 좀 걸렸다.

bfs는 2차원 배열에서 주로 풀다보니까 1차원 배열에서 bfs를 쓴다는 생각을 못 했다.

단순하게 1차원 배열에서 주어진 조건에 따라 이동하면서 배열의 값을 1씩 증가 시키다가

동생을 만나면 종료하고 해당 인덱스의 값을 출력하는 식으로 풀었다.

코드에 주석을 달아놓았다!

package sliver;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_1697{

	/*
	 * 수빈이의 현재 위치에서
	 * 동생을 찾으러 가는데 걸리는
	 * 최단 시간 구하는 문제
	 * 1초에 +1, -1
	 * 순간이동 2*x
	 * 10만 짜리 배열을 미리 만들어놓고
	 * 3가지 경우를 체크해가면서 bfs 돌려보자
	 */
	
	static int N; //수빈이 시작 위치
	static int K; //동생 위치
	static int [] arr; //길찾기 배열

	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		//수빈이 위치
		N = sc.nextInt();
		//동생 위치
		K = sc.nextInt();

		//배열의 크기가 10만까지임
		//인덱스랑 크기 맞출려고 +1 해줬다
		arr = new int [100001];
		
		bfs(N, K);
		
		//수빈이의 처음 위치에 1을 더하고 시작했으니까
		//출력 시에는 1을 빼야함
		System.out.println(arr[K]-1);
		
	}
	
	public static void bfs(int n, int k) {
		//큐 생성
		Queue<Integer> q = new LinkedList<>();
		
		//수빈이의 위치를 우선 넣어준다
		q.offer(n);
		//수빈이가 있다는 것을 표시하기 위해서 배열에 1을 넣어준다
		arr[n] = 1;
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			//동생을 만나면 종료하는 조건문이다
			if(cur == K) {
				break;
			}
			
			//앞으로 한칸 이동하는 경우
			int front = cur + 1;
			
			//뒤로 한칸 이동하는 경우
			int back = cur - 1;
			
			//순간이동으로 2배 이동하는 경우
			int twice = cur * 2;
			
			//세가지 경우의 조건을 각각 풀어서 구현하였다
			
			//범위 내에 있고 해당 인덱스가 비어있으면 갈 수 있음
			//출발한 위치에서 +1 한 값을 넣어준다
			if(front >= 0 && front < arr.length && arr[front] == 0) {
				q.offer(front);
				arr[front] = arr[cur]+1;
			}
			
			//밑에도 동일한 조건으로 구한다
			
			if(back >= 0 && back < arr.length && arr[back] == 0) {
				q.offer(back);
				arr[back] = arr[cur]+1;
			}
			
			if(twice >= 0 && twice < arr.length && arr[twice] == 0) {
				q.offer(twice);
				arr[twice] = arr[cur]+1;
			}
		}
	}

}