[백준_1697번] 숨바꼭질

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는 정수이다.

 

[코드]

import java.util.*;

public class BaekJoon_1697 {
	static int start, end;
	static int[] time=new int[100001];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		start=sc.nextInt();
		end=sc.nextInt();
		
		BFS();
		
		if(start==end)
			System.out.println(0);
		else
			System.out.println(time[end]);
	}
	
	// 범위가 크기 때문에 BFS 사용
	static void BFS() {
		Queue<Integer> q=new LinkedList<>();
		q.offer(start);
		time[start]=0;
		
		while(!q.isEmpty()) {
			int now=q.poll();
			
			for(int i=0;i<3;i++) {
				int next;
				
				if(i==0)
					next=now+1;
				else if(i==1)
					next=now-1;
				else
					next=now*2;
				
				//System.out.println(next);
				if(next==end) {
					time[next]=time[now]+1;
					return;
				}
					
				if(next>=0&&next<time.length) {
					if(time[next]==0) {
						q.offer(next);
						time[next]=time[now]+1;
					}
				}
			}
		}
	}
}

 

[고찰]

 이번 문제를 어떻게 bfs로 풀어야할지 고민을 많이 해봤지만 해답이 떠오르지 않아 다른 사람의 포스팅을 참고하였다. 해답은 시작 지점으로부터 갈 수 있는 +1, -1, *2인 지점을 모두 탐색하는 것이다. 계산된 다음 지점이 갈 수 있는 범위내에 있고, 탐색하지 않았다면 큐에 삽입하고, 이전 일수 +1을 해준다. 처음에는 이해가 잘 되지 않아 그림으로 그려보았다. 수빈이가 5에서 시작하여 17에 도착하는 주어진 예제를 그림을 그려본다면 아래와 같을 것이다.

 

0초

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
값					1

 

1초

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
값				2	1	2				2

5에서 이동 가능한 4,6,10의 값을 5의 인덱스 값의 +1한 값으로 갱신한다.

 

2초

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
값			3	2	1	2	3	3	3	2	3	3

4,6,10에서 각각 이동 가능한 값을 3으로 갱신해준다. 이때 3에서 4로 이동 가능하지만 이미 2라는 값이 저장되어 있기 때문에 방문한 인덱스의 값은 갱신하지 않는다.

 

3초

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
값		4	3	2	1	2	3	3	3	2	3	3	4	4		4

 

4초

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
값	5	4	3	2	1	2	3	3	3	2	3	3	4	4	5	4	5

시작 인덱스의 값을 1부터 시작했기 때문에 결과 값에 -1을 한 4초가 정답이 된다. 이렇게 그림을 그려보면 위의 알고리즘을 쉽게 이해할 수 있을 것이다.