boj 2412 암벽 등반

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

 

(0, 0) 좌표에서 출발하여 주어진 좌표만을 이용해서 목적지인 y = E에 도착하는 최소 이동횟수를 구하는 문제입니다.

좌표 범위가 x * y = 1000000 * 200000 이라 배열로는 해결할 수 없습니다.

그래서 홈이 있는 좌표는 set으로 관리하도록 합니다.

set에는 같은 y좌표들 기준으로 x 좌표를 모아주시면 됩니다. (목적지가 y=E이라 y 좌표 기준)

 

이동은 x, y 각각 -2 ~ +2 범위 내에서만 이동이 가능하고, 범위 내에 홈이 있다면 해당 홈을 지우고 queue에 넣어주시면 됩니다.

일반적으로 bfs는 visit 배열을 사용하여 방문처리를 하지만 범위가 너무 크기 때문에 set에 있는 원소를 지우는 방식으로 방문처리를 대신할 수 있습니다.

 

 

#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#define MAX 200001
using namespace std;
typedef pair<int, int> pii;
 
set<int> s[MAX];
int N, E;
 
int bfs(int sx, int sy) {
    queue<pii> q;
    q.push({ sx,sy });
    for (int t = 0; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (y == E) return t;
 
            for (int ny = max(0, y - 2); ny <= min(E, y + 2); ny++) {
                for (int nx = max(0, x - 2); nx <= x + 2; nx++) {
                    if (s[ny].find(nx) == s[ny].end()) continue;
                    q.push({ nx,ny });
                    s[ny].erase(nx);
                }
            }
        }
    }
 
    return -1;
}
 
void func() {
    cout << bfs(0, 0) << '\n';
}
 
void input() {
    int x, y;
    cin >> N >> E;
    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        s[y].insert(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}