[2412번] 암벽 등반

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

2. lower_bound

이 문제를 풀기 위해 예제입력부터 보자.

5 3
1 2
6 3
4 1
3 2
0 2

0,0->1,2->3,2->4,1->6,3으로 가면 총 4번만에 정상으로 갈 수 있다가 된다.

5 3
4 1
1 2
3 2
0 2
6 3

다음과 같이 y에 대해 오름차순 정렬을 해보자.

그럼 우리는 현재 y좌표일때 y-2부터 y+2까지보면 된다고 설정할 수 있게 된다.

이 방법을 이용하여 이제 문제에 적용해보자.

문제 접근은 최단거리이기에 bfs로 접근할 것이고, b == m이 되면 값을 출력하고 break를 걸면 된다.

bfs과정이기에 거리가 계속해서 최단거리 기준으로 갱신된다.

이제 현재 등반자의 위치 a,b에서 b - 2위치 인덱스부터 우리는 조사를 하면 될 것이다.

예를들어 현재 위치가 2,5이면

5 7
0 2
1 3
2 4
3 5
4 7

여기서 우리가 찾고자 하는 것은 5-3인 y값이 3인곳부터 찾으면 된다.

즉, 1,3부터 찾기 시작하면 된다는 의미이다.

1부터 y가 5이하일때 까지 for문을 돌되, x도 -2칸 +2칸을 만족하는것에 대해 queue에 push를 해주면 된다.

이 과정을 bfs로 돌리면 문제를 해결할 수 있다.

이제 코드를 통해 확인해보자.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <map> #include <cmath>   using namespace std;   typedef pair<int, int> pii;   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() {     int n, m; // m이 정상     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)     {         int a, b;         scanf("%d %d", &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 });         }     }       printf("%d", ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus