[백준/자바] 12851 숨바꼭질 2

12851 숨바꼭질 2 사진 클릭시 문제로 이동

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다.

수빈이는 현재 점 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 2

---

설명

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

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

2021/01/15 - [프로그래밍 문제/백준] - [백준/자바] 1697 숨바꼭질

[백준/자바] 1697 숨바꼭질

문제와 다른 점은 가장 빠른 시간으로 동생을 찾는 가짓수도 함께 구해야 한다는 점이다.

 

해당 예제에서 답은 다음처럼 2가지 경우가 나온다.

5 -> 10 -> 9 -> 18 -> 17

5 -> 4 -> 8 -> 16 -> 17

 

우선 수빈이 동생보다 큰 값에 서있다면 수빈은 동생에게 가장 최소의 시간으로 가기 위해서는 X-1을 해서 가는 방법밖에 없다.

따라서 해당 경우를 예외로 처리해준다.

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

이 문제 역시 X+1, X-1, X*2로 이동시 모두 동일하게 1초를 소요한다.

 

변수는 다음과 같이 지정했다.

check	가지치기의 값이 최소 시간을 의미하므로 최소 시간보다 큰 가지를 배제하기 위한 변수
seconds[]	해당 칸에 소요된 시간을 저장하는 배열
dx[]	X+1, X-1, X*2 이동시 X값을 움직이기 위한 배열
count	동생의 위치에 도착한 가지수를 세는 변수

 

check의 값은 Integer.Integer.MAX_VALUE에서 동생의 위치가 되면 해당 위치의 seconds 값으로 변하게 된다.

이때 check는 동생의 위치까지 도달하기 위한 최소의 시간이 되기 때문에 q를 확인하다 check보다 큰 값의 경우 최소 시간에 위배되기 때문에 return 하게 된다.

 

이 문제는 가짓수를 구하는 문제이기 때문에 중복된 값을 포함해서 값을 구해야 한다.

다만 이 중복된 값은 이전에 구한 seconds의 값이 지금 현재 seconds값 + 1 일 때만 가능한다.

예를 들어보자면

1 4

의 경우 1 -> 2 (X+1) -> 4 (X*2)1 -> 2 (X*1) -> 4 (X*2)로 두가지 경우가 있다.

 

이때 첫번째 경우에서 2의 값을 중복 허용하지 않았다면 두 번째 경우는 고려할 수 없게 된다.두 가지 경우 모두 1에서 1번의 가지치기로 각각 2 (X+1)와 2 (X*1)에 도달하는 점을 고려한다면seconds의 값이 지금 현재 seconds값 + 1 일 때만 가능하다는 것을 알 수 있다.현재 seconds[2]의 값이 X+1을 통해 1이 되고다음 X*1을 통해 생성된 seconds[2]도1이기 때문에 다시 q에 넣어주게 된다.

 

 

해당 사항은 다음과 같은 코드를 통해 확인할 수 있다.

if(seconds[x] == 0 || seconds[x] == seconds[cur] + 1) {
	q.add(x);
	seconds[x] = seconds[cur] + 1;
}

코드