[BOJ] 12851 숨바꼭질 2 C++

개요

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

12851번: 숨바꼭질 2

골드4 탐색 문제다.

풀이

1697번 숨바꼭질

위 문제와 거의 유사하고, 차이점으로 가장 빠른 방법의 수를 추가로 출력해주어야 한다.

가장 빠른 경로가 탐색이 됐을 때, ans 변수에 시간(cnt)을 저장한다.

만약 도착지에 도착했을 때 걸린 시간과 ans의 시간이 일치할 경우 경우의 수(ansCnt)를 증가시킨다.

시간이 ans를 넘은 경우의 수는 continue 한다. (시간 초과 방지)

 

한 번 방문했던 곳은 다시 못 가게 해서 한 번 틀렸다.

방문했던 곳(visited)을 bool에서 int로 바꾸어 주었다.

방문하면 cnt를 visited[x]에 대입해준다.

다시 방문했을 때 이전 방문 했던 시간보다 크지 않다면 탐색을 이어나가게 해주었다.

코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
constexpr int LIMIT = 100000;

struct Info
{
	int x;
	int cnt;
};
int N, K;
int visited[LIMIT + 2];
int ans = LIMIT + 2;
int ansCnt;

void BFS()
{
	queue<Info> q;
	q.push({ N, 0 });

	while (!q.empty())
	{
		auto [x, cnt] = q.front();
		q.pop();

		if (ans < cnt) continue;
		if (x < 0 || x > LIMIT) continue;
		if (x == K)
		{
			ansCnt++;
			ans = cnt;
		}

		if (visited[x] < cnt) continue;
		visited[x] = cnt;
		q.push({ x - 1, cnt + 1 });
		q.push({ x + 1, cnt + 1 });
		q.push({ x * 2 , cnt + 1 });
	}
}


int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K;

	for (auto& v : visited)
		v = LIMIT + 2;

	BFS();

	cout << ans << "\n" << ansCnt;
}