[백준] 2412번: 암벽 등반

문제

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

2412번: 암벽 등반

문제 해결

BFS + 이분 탐색(lower_bound)

 

결과

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
using namespace std;

using pii = pair<int, int>;
vector<pii> arr;
map<pii, bool> visit;
int ans = -1;

bool comp(const pii& a, const pii& b)
{
	return a.second < b.second;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n = 0, m = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		arr.push_back({ a,b });
	}

	sort(arr.begin(), arr.end(),comp);

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

	while (!q.empty())
	{
		int a = q.front().first.first;
		int b = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (b == m)
		{
			ans = cnt;
			break;
		}

		if (visit[{a, b}]) continue;
		visit[{a, b}] = true;

		auto it = lower_bound(arr.begin(), arr.end(), pii(0, b - 2), comp) - arr.begin();

		for (int i = it; i < n && abs(arr[i].second - b) <= 2; i++)
		{
			int x = arr[i].first;
			int y = arr[i].second;

			if (!visit[{x, y}] && abs(x - a) <= 2)
				q.push({ {x,y},cnt+1 });
		}
	}
	cout << ans;
	return 0;
}