[백준][C++] 13549 숨바꼭질 3

13549. 숨바꼭질 3
문제 풀이

13549번: 숨바꼭질 3

기존 숨바꼭질에서 조건 하나만 바뀐 문제. 2 * X로 순간 이동할 때 1초가 아닌 0초 걸리는 것으로 바꿨다.

 

기존 코드에서 2*x하는 부분과 min값을 구하는 부분만 수정하면 되어서 어렵지 않았다.

 

알고리즘 설계

https://minyoung529.tistory.com/19

코드

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

#define MAX 100000
bool visited[100001];
int start, endV, answer = 10000000;

void set(int f, int s, queue<pair<int, int>>& q)
{
	if (f < 0 || f > MAX || visited[f]) return;

	visited[f] = true;
	q.push({ f , s });
}

int main()
{
	cin >> start >> endV;

	queue<pair<int, int>> q;
	q.push({ start, 0 });

	if (start >= endV)
	{
		cout << start - endV;
		return 0;
	}

	while (!q.empty())
	{
		pair<int, int> top = q.front();

		// 찾았다면 종료  
		if (top.first == endV)
		{
			answer = min(top.second, answer);
		}

		q.pop();

		if (top.first != 0)
			set(top.first * 2, top.second, q);

		set(top.first - 1, top.second + 1, q);
		set(top.first + 1, top.second + 1, q);
	}

	cout << answer;
}

재미있는 BFS 문제였다!!