백준 14630번: 변신로봇 (C++)

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

14630번: 변신로봇

---

Solved By: Dijkstra

 

오래간만에 풀어본 다익스트라 문제였습니다. 변신 상태를 각각 하나의 노드로 취급했을 때, 각 엣지들의 가중치는 각 노드에 입력받은 값들을(문자열로) 각 자리의 차를 제곱한 값들을 더해주었습니다. 가중치들을 각 노드의 엣지로 이어주는 방법은 Brute-Force를 택했습니다.

 

(거의 3달 전에 작성했던 코드(틀림)과 비교해봤더니 신기하더군요. 그런데 3달 전이면 저 이병 때네요. 사회에 있을 때 시도한 줄..)

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#define INF 1e9
#define MAX 1001
#define pii pair<int, int>
using namespace std;

vector<pii> adj[MAX];
string change[MAX];
int n;

struct cmp{
    bool operator()(pii a, pii b){
        return a.second > b.second;
    }
};

void swap(string* a, string* b){
    string* temp = a;
    a = b;
    b = temp;
}

int getCost(string a, string b){
    if(a.length() < b.length()) swap(a, b);
    
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    while(b.length() < a.length()){
        b += '0';
    }
    
    int ret = 0;
    for(int i = 0; i < a.length(); i++){
        ret += pow((a[i] - '0') - (b[i] - '0'), 2);
    }
    
    //cout << ret << '\n';
    return ret;
}

vector<int> dijkstra(int node){
    vector<int> dist(n + 1, INF);
    priority_queue<pii, vector<pii>, cmp> pq;
    
    pq.push({node, 0});
    dist[node] = 0;
    
    while(!pq.empty()){
        int now = pq.top().first;
        
        pq.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            int nextCost = adj[now][i].second;
            
            if(dist[now] + nextCost < dist[next]){
                dist[next] = dist[now] + nextCost;
                
                pq.push({next, dist[next]});
            }
        }
    }
    
    return dist;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> change[i];
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) continue;
            int w = getCost(change[i], change[j]);
            adj[i].push_back({j, w});
            adj[j].push_back({i, w});
        }
    }
    
    int from, to; cin >> from >> to;
    
    vector<int> res = dijkstra(from);
    
    cout << res[to];
    return 0;
}