2412 / 암벽 등반

암벽 등반

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	873	210	144	24.324%

문제

어떤 암벽에 n(1≤n≤50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a-x|≤2이고 |b-y|≤2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동하면서 y=T(1≤T≤200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다.

현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다. 정상에 오를 때의 x좌표는 아무 것이나 되어도 상관이 없다.

입력

첫째 줄에 n, T가 주어진다. 다음 n개의 줄에는 각 점의 x, y좌표가 주어진다. 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하이다. 입력에 현재 위치인 (0, 0)은 주어지지 않는다.

출력

첫째 줄에 최소 이동 회수를 출력한다. 만약, 정상에 오를 수 없으면 -1을 출력한다.

---

BFS + 응용문제.

길이가 4 x 4인 정 사각형의 각 대각선의 교점이 현재 위치가 된다고 생각하면 된다.

즉, 자신의 위치를 중심으로 사각형을 그렸을 때, 그 내부의 모든 점을 Queue에 넣으면서 위로 올라가면 된다.

큐에 넣을 때 주의할 점은, 이미 방문한 점은 더 적은 횟수로 이미 도착할 수 있는 점이기 때문에 visit처리를 해주어야 중복을 막을 수 있다는 점이다.

핵심은

1. 입력 받은 모든 점들을 y좌표의 오름차순(같은 경우 x의 오름차순 정렬)으로 먼저 정렬 해주어야 함

2. 자신의 인덱스를 기준으로 상, 하, 좌, 우 거리가 2인 모든점을 탐색해야 하므로 큐에 자신의 인덱스를 같이 넣어주고 양 방향으로 탐색해주어야 시간초과가 나지 않음.

3. 오름차순으로 정렬했기 때문에 범위가 사각형을 벗어나는 순간 그 이후 모든 점은 사각형의 범위 밖이므로 탐색하며 큐에 넣을 필요가 없음.

[Code]

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<utility>
#include<algorithm>
#include<queue>
#define P pair<int,int>
#define PP pair<P,P>
#define mp(a,b) make_pair(a,b)
using namespace std;
 
int n, t, res;
P arr[50001];
bool visit[50001];
 
int bfs();
 
bool cmp(P a, P b) {
    if (a.second == b.second) return (a.first < b.first);
    else return (a.second < b.second);
}
 
int main() {
 
    scanf("%d%d", &n, &t);
 
    for (int i = 0; i < n; i++) 
        scanf("%d%d", &arr[i].first, &arr[i].second);
    
    sort(arr, arr + n, cmp);
 
    printf("%d\n", bfs());
 
    return 0;
}
 
int bfs() {
    queue<PP> Q;
    Q.push(mp(mp(0, 0), mp(0,0)));
 
    while (!Q.empty()) {
        int cx = Q.front().first.first;
        int cy = Q.front().first.second;
        int cnt = Q.front().second.first;
        int idx = Q.front().second.second;
        Q.pop();
 
        if (cy == t) return cnt;
 
        for (int i = idx; i < n; i++) {
            int nx = arr[i].first;
            int ny = arr[i].second;
            if (!visit[i]) {
                if ((abs(cx - nx) <= 2) && (abs(cy - ny) <= 2)) {
                    visit[i] = true;
                    Q.push(mp(mp(nx, ny), mp(cnt + 1, i)));
                }
                else if ((abs(cx - nx) > 2) && (abs(cy - ny) > 2)) break;
            }
        }
 
        for (int i = idx; i >= 0; i--) {
            int nx = arr[i].first;
            int ny = arr[i].second;
            if (!visit[i]) {
                if ((abs(cx - nx) <= 2) && (abs(cy - ny) <= 2)) {
                    visit[i] = true;
                    Q.push(mp(mp(nx, ny), mp(cnt + 1, i)));
                }
                else if ((abs(cx - nx) > 2) && (abs(cy - ny) > 2)) break;
            }
        }
 
    }
 
    return -1;
}