[BaekJoon][2412] 암벽 등반

BAEKJOON ONLINE JUDGE

2412 암벽 등반

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

이진탐색 문제집에서 본 문제지만

bfs로도 풀리는 문제

탐색 시간을 줄이기 위해 x, y를 오름차순 정렬

자신의 x와 왼쪽으로 2보다 작은 지점들만 검사, +2 보다 작은 지점들만 검사하여 시간을 줄임

-> y도 x에 따라서 정렬을 한 후에 이진탐색으로 위치를 찾아서 거기까지만 탐색하게 하면 시간을 더 줄일 수 있을 듯

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int n, t;
vector<pair<int, int> > point;
int visit[50001];
 
int myabs(int n) {
    if (n < 0)    return n * -1;
    return n;
}
 
int bfs()
{
    queue<int> que;
    que.push(0);
    visit[0] = 1;
 
    while (!que.empty()) {
        int idx = que.front();
        que.pop();
 
        if (point[idx].second == t) {
            return visit[idx] - 1;
        }
 
        for (int i = idx - 1; i > 0; i--) {
            if (myabs(point[i].first - point[idx].first) > 2)    break;
            if (visit[i] == 0 && myabs(point[i].second - point[idx].second) <= 2) {
                visit[i] = visit[idx] + 1;
                que.push(i);
            }
        }
        for (int i = idx + 1; i <= n; i++) {
            if (myabs(point[i].first - point[idx].first) > 2)    break;
            if (visit[i] == 0 && myabs(point[i].second - point[idx].second) <= 2) {
                visit[i] = visit[idx] + 1;
                que.push(i);
            }
        }
    }
 
    return -1;
}
 
int main()
{
    int x, y;
 
    scanf("%d %d", &n, &t);
 
    point.push_back(make_pair(0, 0));
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &x, &y);
        point.push_back(make_pair(x, y));
    }
 
    sort(point.begin(), point.end());
 
    printf("%d\n", bfs());
 
    return 0;
}