BOJ 31885 : Yunny's Trip

• 문제 링크 : boj.kr/31885
• 난이도 : G3
• 태그 : 애드혹, set

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll dist(pll a, pll b) {
    return abs(a.first-b.first) + abs(a.second-b.second);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;
    set<pll> _s;
    for(int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        _s.insert(pll(a,b));
    }
    pll dest;
    cin >> dest.first >> dest.second;
    ll ans = k+1;
    for(auto u : _s) {
        pll curr = u;
        ll sp = 2 + dist(curr, dest);
        ans = min(ans, sp);
        pll temp = {dest.first-curr.first, dest.second-curr.second};
        if(_s.find(temp) != _s.end()) {
            ans = min(ans, 4ll);
        }
        if(_s.find(pll(temp.first-1, temp.second)) != _s.end()) {
            ans = min(ans, 5ll);
        }
        if(_s.find(pll(temp.first+1, temp.second)) != _s.end()) {
            ans = min(ans, 5ll);
        }
        if(_s.find(pll(temp.first, temp.second-1)) != _s.end()) {
            ans = min(ans, 5ll);
        }
        if(_s.find(pll(temp.first, temp.second+1)) != _s.end()) {
            ans = min(ans, 5ll);
        }
    }
    ans = min(ans, dist(pll(0,0), dest));
    cout << (ans > k ? -1 : ans);

    return 0;
}

---

풀이

아이템을 최대 2번까지 사용할 수 있기 때문에 아이템의 사용 횟수를 기준으로 나눈다.

아이템을 0번 사용할 경우 원점으로부터 목적지까지의 거리가 5 이내라면 도달 가능하다.

아이템을 1번 사용할 경우, 임의의 아이템을 사용한 후 목적지까지의 거리가 3 이내라면 도달 가능하다.

아이템을 2번 사용하는 경우는 좀 복잡하다. O(N^2)으로 아이템을 선택할 경우 시간초과가 발생한다. 따라서 임의의 아이템을 사용하고, 해당 위치에서 목적지까지 거리 1 이내에 도달할 수 있는 아이템이 있는지 확인한다. 자료구조 set을 사용할 경우 O(logN)이내로 가능하다.

도달할 수 있는 모든 경우 중 최소로 사용한 에너지가 답이 된다.