C++ / 12851 / 숨바꼭질 2 ( 너비 우선 탐색 )

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

문제 요약

수빈이는 동생과 숨바꼭질을 하고 있습니다. 수빈이는 현재 점 n에 있고, 동생은 점 k에 있습니다. 수빈이는 걷거나 순간이동을 할 수 있습니다.

만약, 수빈이의 위치가 x일 때 걷는다면 1초 후에 x - 1 또는 x + 1로 이동하게 됩니다. 순간이동을 하는 경우에는 1초 후에 2 * x의 위치로 이동하게 됩니다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시가능로 찾는 방법이 몇가지 인지 구하는 프로그램을 작성해야 합니다.

 

이 문제는 숨바꼭질 1과 이어지는 문제입니다.

https://lgj415415.tistory.com/72

C++ / 1697 / 숨바꼭질 ( 너비 우선 탐색 )

 

문제 풀이

1. 좌표별로 최단시간을 담을 배열, 방문체크 배열, 좌표별로 경우의 수를 담을 배열을 만듭니다.

2. 수빈이와 동생의 위치를 입력받습니다.

3. bfs 함수를 만드는데 매개변수로 시작좌표( 수빈 )을 받습니다. 경우의 수 배열의 시작 좌표 인덱스는 1로 초기화 합니다.( 시작 좌표부터 시작좌표까지 가는 경우의 수는 1이기 때문 )

4.숨바꼭질 1과 동일하게 1적을 때, 1많을 때, 2배일 때 순으로 탐색을 합니다.

5. 탐색중에 범위 내의 방문하지 않은 지역에서는

최단 시간 배열에 이전항으로부터의 가중치를 더해주고, 경우의 수 배열에는 이전 경우의수를 거듭 더해줍니다.

이전 경우의 수를 거듭 더해주는 이유는 1에서 2로가는 경우의수가 1+1 1*2로 두가지가 생기기 때문입니다.

6. 방문하지 않았으면서 최단시간인 경우에도 경우의 수 배열을 이전 경우의수를 거듭 더해줍니다.

( 해당 좌표에 갈수있는 최단 경로의 경우의 수 )

7. 만들어진 최단시간 배열과 경우의 수 배열에 동생의 위치를 넣어 출력합니다.

주의할 점

이 문제는 경우의 수 배열을 만드는 것과 경우의 수 배열에 이전 경우의 수를 거듭 더해주는 것이 중요합니다.

위에도 설명했지만  1 부터 2까지 가는 방법이 1+1과 1*2로 두가지가 있기때문에 n이 1인 경우에는 모든 경우의수가 거듭해서 생길 수 있습니다.

그 외의 경우에서는 거듭 더해주지 않고 cnt[nx] += 1로 단순히 1만 더해줘도 결과가 나오기 때문에 헷갈릴 수 있습니다.

코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;


int ans[100001];
int cnt[100001];
bool visit[100001];
int n, k;

void bfs(int x)
{
	visit[x] = true;
	ans[x] = 0;
	// 처음에 도달한 경우의 수 1
	cnt[x] = 1;
	queue<int> q;
	q.push(x);

	while(!q.empty())
	{
		x = q.front();
		q.pop();
		for (int nx : {x - 1, x + 1, x * 2})
		{
			if (nx > 100000 || nx < 0)
			{
				continue;
			}
			// 경우의 수는 1이 2가 되는 방법이 +1, *2로 두가지로 생기기 때문에 전에 있던 값을 더해줌
			if (!visit[nx])
			{
				visit[nx] = true;
				ans[nx] = ans[x] + 1;
				cnt[nx] += cnt[x];
				q.push(nx);
			}
			else if (ans[nx] == ans[x] + 1)
			{
				cnt[nx] += cnt[x];
			}
		}
	}

}
int main()
{
	cin >> n >> k;
	bfs(n);
	cout << ans[k]<< '\n';
	cout << cnt[k];
	return 0;
}

반응형

예제 

5 17

결과

1이 2개 필요한 경우( n = 1 )의 예제

1 14

결과

1부터 14에 도달하는 경우의 수는 

{ 1, 2, 4, 8, 7, 14 }

{ 1, 2, 3, 6, 7, 14 }

로 경우의 수는 2가 나오지만 1에서 2로 갈때 1+1과 1*2로 두가지 방법이 있기 때문에 4가 나와야합니다.