BOJ13549_숨바꼭질3

다익스트라 사용한다고 무조건 이중 vector 넣을 필요 없음.

이 문제의 경우 graph에 각각 3개의 간선 넣었더니 runtime error

graph 대신 조건문으로 바꿨더니 메모리 초과  안남

 

이후 또 틀렸는데 if(b > k * 2) 라는 이상한 조건문 넣어서 틀림

 

// graph 에 각각 3개의 간선 넣으면 runtime error
// graph 대신 조건문으로 bad alloc 없앰
// if(b > k * 2) 라는 이상한 조건문 넣어서 틀림

#include <iostream>
#include <queue>
#include <vector>
#define INF int(1e5)

using namespace std;

struct Edge {
    int to;
    int cost;
};

struct cmp {
    bool operator() (Edge a, Edge b) {
        if (a.cost <= b.cost) return false;
        else return true;
    } 
};

int n, k;
int d[100001];
// 각 노드마다 간선이 3가지 있다고 가정
// +1, -1 : 가중치 +1
// *2 : 가중치 0

void dijkstra() {
    priority_queue<Edge, vector<Edge>, cmp> pq;
    pq.push({n, 0});        // 수빈의 위치
    d[n] = 0;

    int X[2] = {-1, 1};

    while(!pq.empty()) {
        Edge cur = pq.top(); //현재 위치, 현재 시간
        pq.pop();

        if (d[cur.to] < cur.cost) continue;

        int b, b_cost;
        for(int i = 0; i < 3; i++) {
            if (i == 2) {
                b = cur.to * 2;
                b_cost = cur.cost;
            } else {
                b = cur.to + X[i];
                b_cost = cur.cost + 1;
            }
            if (b < 0 || b > 100000) continue;
            if (d[b] <= b_cost) continue;

            d[b] = b_cost;
            pq.push({b, b_cost});
        }
    }
}


int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k;
    
    // 비용 배열 초기화
    for (int i = 0; i <= 100000; i++) {  
        d[i] = INF; 
    }

    dijkstra();

    cout << d[k] << endl;
}