[BOJ] 1697: 숨바꼭질(JAVA)

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 

5 17

예제 출력 1

4

---

[문제 풀이]

BFS를 이용하여 해결하면 되는 문제이다.

현재 위치에서 -1, +1, *2의 위치를 탐색한다.

만약 다음 탐색할 위치가 범위 내의 좌표이고, 아직 탐색한 적이 없다면 Queue에 넣어주고 v[다음 탐색할 위치] 값을 현재 위치+1로 업데이트한다. (현재 위치에서 다음 위치로 이동하는 것은 1초가 걸리기 때문)

큐에 원소가 아무것도 없거나 다음 탐색할 위치가 동생의 위치(K)일 때까지 정수 배열 v값을 업데이트한다.

 

1. 수빈이의 위치가 처음부터 동생의 위치와 같다면 0을 출력하고 종료한다.

2. 그렇지 않다면, bfs 함수를 진행한다.

    2-1. 수빈이와 동생의 위치 값의 범위는 0~100000이므로 정수 배열 v의 크기를 100001로 선언한다. v에는 초기 수빈이의 위치부터 v배열의 인덱스까지 이동하기 위해 걸리는 시간을 저장할 것이다.

 

 

 

[코드]

import java.util.*;
public class Main{
	static int N, K;
	static int[] v = new int[100001];
	static int[] dx = {-1, 1};
	
	public static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(N);
		v[N]=1;
		
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			
			for(int i=0;i<3;i++) {
				int nx;
				if(i==2)
					nx = cur*2;
				else
					nx = cur + dx[i];
				
				if(nx==K) {
					System.out.println(v[cur]);
					return;
				}
					
				if(nx>=0 && nx<v.length && v[nx]==0) {
					queue.add(nx);
					v[nx] = v[cur]+1;
				}
			}
		}
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K =sc.nextInt();
		if(N==K)
			System.out.println(0);
		else {
			bfs();
		}
	}
}