[BOJ] 13549 숨바꼭질 3 C++

개요

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

13549번: 숨바꼭질 3

골드5 탐색 문제다.

풀이

1697번 숨바꼭질

위 문제와 거의 유사하지만 순간이동을 할때 시간이 증가하지 않는 다는 차이점이 있다.

똑같이 BFS로 풀었지만, 순간이동을 먼저 큐에 넣어주어 경우의 수를 먼저 탐색할 수 있도록 했다.

코드

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

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

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

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

		if (x == K)
		{
			ans = cnt;
			return;
		}

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


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

	cin >> N >> K;

	BFS();

	cout << ans;
}