[백준] 숨바꼭질2 (12851번)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

---

쉽게 생각했다가 오답이 떠서 고생한 문제이다.

숨바꼭질 1 문제에서 푼 것 처럼 거리를 나타내는 배열 p로 방문 여부를 확인했었는데, 아예 거리를 나타내는 배열과 방문 여부를 나타내는 배열을 따로 두는 게 더 직관적이고 문제 풀기도 좋은 것 같다. 거기에 이 문제는 최소시간으로 가는 방법의 수까지 알아내야하기 때문에 그 방법을 세는 배열까지 만들었다. 

문제 푸는 방법은 1과 비슷하다. 방문한 적이 없으면 거리를 최신화하고 방문여부를 true로 바꾼다. cnt는 이전에 방문한 지점의 cnt로 똑같이 설정한다. 차이가 있다면 이미 방문한 적이 있는 지점중에 거리가 1만 차이나는 곳은 cnt를 더해줘야한다.

예를들어,

1 -> 2(+1) -> 4(*2) 와

1 -> 2(*2) -> 4(*2) 는 다른 1에서 4까지 가는 다른 방법이기 때문에 정답으로 2를 출력해야 한다. 그러므로 처음 +1해서 2에 도달했을 떈

cnt[2] = cnt[1]로 선언하고, 두번째 1에 2를 곱해서 2에 도달했을 땐 방문은 했지만, dist[2] == dist[1]+1이므로 cnt[2] += cnt[1]을 하면 방법의 수가 2가 되는 것이다. 이 점만 유의하면 문제를 해결할 수 있다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%882(12851).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int N, K, res;
int dist[100001];
int cnt[100001];
bool chk[100001];

void bfs()
{
	queue<int> q;
	q.push(N);
	dist[N] = 0;
	cnt[N] = 1;
	chk[N] = true;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (x + 1 <= 100000) {
			if (!chk[x + 1]) {
				dist[x + 1] = dist[x] + 1;
				chk[x + 1] = true;
				q.push(x + 1);
				cnt[x + 1] = cnt[x];
			}
			else if(dist[x+1]==dist[x]+1)
				cnt[x + 1] += cnt[x];
		}
		if (x * 2 <= 100000) {
			if (!chk[x * 2]) {
				dist[x * 2] = dist[x] + 1;
				chk[x * 2] = true;
				q.push(x * 2);
				cnt[x * 2] = cnt[x];
			}
			else if (dist[x * 2] == dist[x] + 1)
				cnt[x * 2] += cnt[x];
		}
		if (x - 1 >= 0) {
			if (!chk[x - 1]) {
				dist[x - 1] = dist[x] + 1;
				chk[x - 1] = true;
				q.push(x - 1);
				cnt[x - 1] = cnt[x];
			}
			else if (dist[x - 1] == dist[x] + 1)
				cnt[x - 1] += cnt[x];
		}
	}
}

int main()
{
	cin >> N >> K;
	memset(cnt, 0, sizeof(cnt));
	memset(chk, false, sizeof(chk));
	bfs();
	cout << dist[K] << endl << cnt[K];
}