[BOJ / BFS] 12851 숨바꼭질 2

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

12851번: 숨바꼭질 2

 

12851 숨바꼭질 2

알고리즘 : BFS / 메모이제이션

일반 BFS 문제에 최단경로의 개수를 추가하여 한 번 뒤섞은 문제입니다. 수빈이와 동생이 같은 자리일 경우도 한 가지의 경우로 치는 것과, 출력 사이에 '\n'이 있음을 유의하지 않아 정답률이 낮은 문제인 것 같습니다. ㅠㅠ

범위 초과에 유의하며 푸시면 좋습니다.

 

 

< CODE >

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

using namespace std;

#define MAX 100000

struct forQ {
	int x;
	int cnt;
};

int visit[MAX + 1];
int when[MAX + 1];
queue<forQ> q;

int n, k;

int solve() {
	visit[n] = 1;
	when[n] = 0;

	if (n == k)
		return 0;

	q.push({ n,0 });

	while (!q.empty()) {
		forQ cur = q.front(); q.pop();

		if (cur.x == k)
			return cur.cnt;

		if (cur.x < k && cur.x * 2 <= MAX)
		{
			if (!visit[cur.x * 2])
			{
				visit[cur.x * 2] = visit[cur.x];
				when[cur.x * 2] = cur.cnt + 1;
				q.push({ cur.x * 2, cur.cnt + 1 });
			}
			else if (when[cur.x * 2] == cur.cnt + 1)
				visit[cur.x * 2] += visit[cur.x];
		}


		if (cur.x < k && cur.x + 1 <= MAX)
		{
			if (!visit[cur.x + 1])
			{
				visit[cur.x + 1] = visit[cur.x];
				when[cur.x + 1] = cur.cnt + 1;
				q.push({ cur.x + 1, cur.cnt + 1 });
			}
			else if (when[cur.x + 1] == cur.cnt + 1)
				visit[cur.x + 1] += visit[cur.x];
		}

		if (cur.x - 1 >= 0)
		{
			if (!visit[cur.x - 1])
			{
				visit[cur.x - 1] = visit[cur.x];
				when[cur.x - 1] = cur.cnt + 1;
				q.push({ cur.x - 1, cur.cnt + 1 });
			}
			else if (when[cur.x - 1] == cur.cnt + 1)
				visit[cur.x - 1] += visit[cur.x];
		}
	}

	return -1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;

	int answer = solve();
	cout << answer << '\n' << visit[k] << '\n';

	return 0;
}

시간 : 0ms

 

태그 : #BOJ 숨바꼭질2 #12851 숨바꼭질2