[백준/자바] 13549 숨바꼭질 3

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

출력

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

예제 입력 1

5 17

예제 출력 1

2

---

설명

해당 문제는 다음 알고리즘 분류에 속하는 문제다.

 

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색

이전 1697 숨바꼭질과 12851 숨바꼭질 2와 다른 점은 X위치에 있는 수빈이가 이동시 X-1과 X+1은 1초가 걸리지만

X*2는 0초가 걸린다는 사실이다.

 

우선 수빈이가 동생보다 큰 값의 위치의 서있는 경우 X-1로만 이동 가능하므로 n-k가 답이 된다.

if(k <= n) {
	System.out.println(n-k);
}

 

이 문제 역시 1697 숨바꼭질문제처럼 가장 빠른 시간만 구하는 문제이기 때문에

12851 숨바꼭질 2처럼 중복을 허용해 문제를 풀 필요가 없다.

따라서 visited배열을 통해 방문했는지 여부를 판단하며 문제를 해결해 나가면 된다.

 

이동하는 거리를 다음과 같은 배열을 사용해 구한다.

String의 앞의 값을 곱하고 뒤의 값은 더해서 사용한다.

static String dx[] = {"2 0", "1 -1", "1 1"};

 

 

이때 뒤의 값의 절댓값을 살펴보면 

X*2 이동 시에는 0이고

X+1과 X-1 이동 시에는 1인 것을 확인할 수 있다.

이 값은 이동했을 때 각각 걸린 시간과 같아서 시간의 값에 더해주는 역할로도 사용했다.

 

 

 

코드