[C++] 백준 12851번 - 숨바꼭질 2

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

12851번: 숨바꼭질 2

BFS문제로 주어진 입력의 현재 위치에서 동생의 위치를 찾으면 동생을 찾는 가장 빠른 시간(최단거리)과 가장 빠른 시간으로 동생을 찾는 방법의 수를 출력하는 문제입니다.

boj 1697번 숨바꼭질 문제에서 방법의 수를 출력하는 조건이 추가된 문제로 해당 문제와 13549번 숨바꼭질 3, 13913번 숨바꼭질 4 문제를 풀고 난 후 시도했기 때문에 특별히 시간이 걸릴 거라고 예상하지 못했던 문제입니다.

처음에 단순히 bfs를 돌릴때 큐에서 위치를 꺼내면서 처음 동생을 발견한 최단 거리를 저장하고(ans = dist [cur]), 이후에 큐에서 뺀 다른 위치에 도착한 최단거리가 동일하면(if(dist [cur]==ans)) count를 세는 방식으로 접근하였는데, bfs를 진행할 때 이미 방문한 위치를 다시 방문하지 않기 때문에 같은 위치가 큐에 두 번 이상 들어가지 않아 이 방법으로는 문제를 해결할 수 없습니다.

또 다른 해결해야하는 문제점으로 다른 방법으로 같은 장소를 이동할 때 이를 따로 세어야 합니다.
예를 들면 장소 1에서 2로 이동하는 경우 이전에는 (1+1 = 2)와 (1 * 2 = 2) 두 가지 방법을 다른 방법으로 구별하지 않았지만, 이번 문제에서는 방법의 수를 출력해야 하기 때문에 위의 두 경우를 다르게 세어야 합니다.

이를 해결하기 위해 cnt배열을 새로 선언합니다.
cnt[i] 는 출발장소(n)에서 i 장소에 도달할 수 있는 방법의 수를 나타냅니다.
cnt[n](n은 시작 장소)는 1로 설정하고, bfs에서 거리를 구할 때 이동하면서 기존의 거리에 1을 더했던 것처럼 해당 위치에 처음 도달한 경우에는 cnt[nx] = cnt[cur] (nx는 새로운 위치)으로 방법의 개수를 저장합니다.
이때 이전에 방문해 cnt[nx]가 0이 아닌 경우에는 최단거리가 같은 경우에 한해(if (dist[cur] + 1 == dist [nx])) 도달할 수 있는 방법의 수를 추가해주고(cnt[nx] += cnt[cur];) bfs가 장소를 중복하여 가지 않도록 continue 해줍니다.
이 외는 기존의 bfs작동 방식과 동일합니다.

마지막으로 dist[k]와 cnt[k]를 각각 출력합니다.

 

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int dist[100002];
int cnt[100002];
queue<int> q;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	if (n == k)
	{
		cout << 0 <<"\n"<<1;
		return 0;
	}

	fill(dist, dist + 100002, -1);

	dist[n] = 0;
	cnt[n] = 1;
	q.push(n);

	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		for (int nx : {cur + 1, cur - 1, cur * 2})
		{
			if (nx < 0 || nx>100000) continue;
			if (dist[nx] != -1)	//방문 했던 곳이면
			{
				if (dist[cur] + 1 == dist[nx])//최단 거리가 같은 경우
					cnt[nx] += cnt[cur];
			}
			else
				//방문을 처음 했다면
			{
				dist[nx] = dist[cur] + 1;	//최단 거리 갱신
				cnt[nx] = cnt[cur];			//처음 간 경우
				q.push(nx);
			}
		}
	}

	cout << dist[k] << "\n" << cnt[k];

	return 0;
}