(C++) - 백준(BOJ) 14496번 : 그대, 그머가 되어

www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

dijkstra로 푼 문제였습니다.

 

풀이방법

 문자 a에서 b로 치환한다면 b에서 a로 치환도 가능합니다. 따라서 무방향 인접리스트로 그래프를 만든 뒤 dijkstra를 시행하면 됩니다. 치환에 걸리는 cost는 1입니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int a, b, n, m;
vector <int> graph[1001];
vector <int> dist(1001);
int dijkstra(){
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    pq.push({0,a});
    dist[a] = 0;
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(cost > dist[cur]) continue;
        for(auto next : graph[cur]){
            if(cost + 1 < dist[next]){
                dist[next] = cost + 1;
                pq.push({cost+1,next});
            }
        }
    }
    if(dist[b] == INF) return -1;
    return dist[b];
}

int main(){
    cin >> a >> b;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) dist[i] = INF;
    for(int i = 0; i < m; i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cout << dijkstra();
}