[BOJ/C++] 2412: 암벽 등반

🏅 Gold 4

✏️ 1차 솔루션

⭐️ BFS

1. (0,0) 에서 시작해서 x, y 좌표 각각에서 2씩 떨어진 좌표는 다음에 갈 수 있는 좌표이므로 큐에 넣기
2. 이미 방문한 경로를 다시 가지 않기 위해 현재 좌표는 visit 처리
3. 이동 횟수 count 가 필요하기 때문에 큐에 저장할 때 현재까지의 count 도 함께 저장해서 관리
4. 현재 방문한 노드가 최종 목적지 높이라면 ans 저장하고 break ➡️ 빨리 도달할수록 최소 이동횟수로 이동한 것이기 때문에 굳이 최소값 비교할 필요 없음

🚨 1차 trouble

시간초과..이분탐색을 필수로 사용해야할 듯. 이분탐색을 어디서 적용할지 감이 안 잡힘

✏️ 최종 솔루션

⭐️ BFS + 이분탐색
⭐️ 각 좌표에서 이동할 수 있는 좌표를 탐색할 때 이분탐색 적용해야 함

• lower_bound 를 사용해서 탐색할 범위를 규정
  ➡️ 다음에 이동할 수 있는 좌표는 y - 2 이상, y + 2 이하이기 때문에 lower_bound 의 탐색값을 pair<int,int>(0,sy-2) 로 설정해서 좌표 중에서 x 값이 0 보다 크고 y 값이 sy - 2 이상인 좌표중에서 가장 먼저 오는 인덱스를 구함
  ❗️ x 범위는 굳이 특정하지 않는 이유는 차순위 순서이기 때문?
• 조건에 해당하는 인덱스부터 다음에 갈 수 있는 y 좌표 조건을 만족하는 범위 한에서 탐색
  ❗️ 이 조건 또 안지키면 시간초과 남;;🤬

📌 self feedback

이분탐색을 활용해야한다는 것을 파악하기가 어려웠던 문제..
탐색범위를 최소화하는 풀이방법으로 그동안 풀었던 이분탐색 문제와는 너무 다르게 lower_bound 를 사용하는 것이 관건이었음
다시 풀어도 못 풀 것 같다..

✏️ 최종 code

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

struct node {
    int x;
    int y;
    int cnt;
};

bool cmp(pair<int,int> p1, pair<int,int> p2) {
    return p1.second<p2.second;
}

int main() {
    int n,t,ans=-1;
    cin >> n >> t;
    vector<pair<int,int>> hole;
    map<pair<int,int>,bool> visit;
    queue<node> q;
    
    for(int i=0;i<n;i++) {
        int x, y;
        cin >> x>> y;
        hole.push_back({x,y});
        visit[{x,y}]=false;
    }
    
    sort(hole.begin(), hole.end(), cmp);
    
    q.push({0,0,0});

    while(!q.empty()) {
        int sx=q.front().x;
        int sy=q.front().y;
        int cnt=q.front().cnt;

        q.pop();

        if(sy==t) {
            ans=cnt;
            break;
        }

        if(visit[{sx,sy}]) continue;

        visit[{sx,sy}]=true;

        auto it = lower_bound(hole.begin(), hole.end(), pair<int,int>(0,sy-2), cmp)-hole.begin();
        
        for(int i=it;i<hole.size()&&abs(hole[i].second-sy)<=2;i++) {

            int nx=hole[i].first;
            int ny=hole[i].second;
     
            if(!visit[{nx,ny}] && abs(nx-sx)<=2 ) {
                q.push({nx,ny,cnt+1});

            }
        }

    }
    
   cout << ans << endl;

}