백준 13549번 숨바꼭질 3 C++

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

 

bfs로 풀었는데, 위치를 찾았는지를 저장하는 found배열을 찾았는지 여부와, 얼마만에 찾았는지 시간의 정보를 함께 저장해서 찾았다고 무조건 건너뛰는 것이 아니라 얼마만에 찾았는지 비교하여서 만약 지금 큐에 넣으려는 경로가 더 빠르다면 이미 찾은 위치라고 하더라도 큐에 넣어주었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, k;
vector<pair<bool, int>> found(100001, { false,0 });

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

	int ans = 987654321;
	cin >> n >> k;
	queue<pair<int, int>> q;
	q.push({ n,0 });
	found[n] = { true,0 };
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();

		if (curr.first == k) {
			ans = min(ans, curr.second);
			continue;
		}

		int next;

		next = curr.first - 1;
		if (next >= 0) {
			if (found[next].first) {
				if (found[next].second > curr.second + 1) {
					q.push({ next,curr.second + 1 });
					found[next] = { true,curr.second + 1 };
				}
			}
			else {
				q.push({ next,curr.second + 1 });
				found[next] = { true,curr.second + 1 };
			}
		}
		
		next = curr.first + 1;
		if (next <= 100000) {
			if (found[next].first) {
				if (found[next].second > curr.second + 1) {
					q.push({ next,curr.second + 1 });
					found[next] = { true,curr.second + 1 };
				}
			}
			else {
				q.push({ next,curr.second + 1 });
				found[next] = { true,curr.second + 1 };
			}
		}

		next = curr.first * 2;
		if (next == 0) continue;
		if (next > 100000) continue;
		if (found[next].first) {
			if (found[next].second <= curr.second) continue;
		}
		q.push({ next,curr.second});
		found[next] = { true,curr.second};
	}
	cout << ans;
};