[백준_13549번] 숨바꼭질 3

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

13549번: 숨바꼭질 3

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

class Point_13549 {
	int point, time;
	
	public Point_13549(int point, int time) {
		this.point=point;
		this.time=time;
	}
}
public class BaekJoon_13549 {
	static boolean[] subin=new boolean[100001];
	static int n,k,min=Integer.MAX_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		
		if(n>=k) // 수빈이의 위치가 더 큰 경우 한칸 뒤로만 이동 가능
			System.out.println(n-k);
		else {
			find(n);
			System.out.println(min);
		}
	}
	
	static void find(int start) {
		Queue<Point_13549> q=new LinkedList<>();
		subin[start]=true;
		q.offer(new Point_13549(start,0));
		
		while(!q.isEmpty()) {
			Point_13549 now=q.poll();
			subin[now.point]=true;
			
			// 동생의 위치에 도달하는 순간 소요시간 갱신
			if(now.point==k)
				min=Math.min(min,now.time);
			
			// 순간이동
			if(now.point*2<=100000&&!subin[now.point*2])
				q.offer(new Point_13549(now.point*2,now.time));
			// 한칸 뒤로 이동
			if(now.point-1>=0&&!subin[now.point-1])
				q.offer(new Point_13549(now.point-1,now.time+1));
			// 한칸 앞으로 이동
			if(now.point+1<=100000&&!subin[now.point+1])
				q.offer(new Point_13549(now.point+1,now.time+1));
		}
	}
}

 

[고찰]

 숨바꼭질 문제는 난이도가 다른 여러 유형이 있는데 이전에 실버 문제를 풀어봤기 때문에 문제의 이해는 어렵지 않았다. 실버 문제와 다른 점은 순간이동은 소요시간이 0초라는 것이다. 처음에는 순간이동인 경우를 모두 먼저 처리해주었지만 메모리 초과 때문에 실패했다. 

 생각해보니 좀 더 간단한 방법이 있었다. 순간이동, 한칸 앞으로, 한칸 뒤로 이렇게 3가지 경우를 모두 고려하다 보면수빈이가 동생이 있는 곳에 도착한 경우가 여러 케이스가 생길 것이다. 그럼 그때마다 최소 시간을 비교해주는 것이다. 이런 방법으로 해결했더니 메모리 초과 없이 정답 처리를 받을 수 있었다.