이번에 포스팅할 문제는
앞에서 다뤘던, 다익스트라 알고리즘을 활용해 푸는 문제입니다.
문제 주소:https://www.acmicpc.net/problem/14496
다익스트라 알고리즘으로 문제를 푼 이유는 일단 시작점(a라는 문자)가 존재하고 도착점(b)로 바꾸기 위해 필요한 치환횟수 이기 때문에,
그래프로 각 치환가능한 쌍을 만들어 놓고, 마지막에 각 a-> 다른 문자로 최소 치환 횟수 d에서
변경하고자 하는 치환 문자에 대한 배열 값을 출력하면 된다.
주의 할 점은 처음에 치환가능 쌍이 주어지면 단방향 그래프로 첫번째 문자에서 ->두번째 문자로의 치환만 가능한 줄 알았는데
한 쌍은 첫번째 문자에서 ->두번째 문자로
두번째 문자에서 ->첫번째 문자로 변경이 가능하다는 것이다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 2147000000
using namespace std;
int a,b,n,m;
vector<pair<int, int>> graph[10001];
int d[1001];
//다익스트라 알고리즘
void dijkstar(int start){
priority_queue<pair<int, int>>pq;
//시작점에 대한 이동비용 0 과 시작점에 대한 노드를 넣는다.
pq.push({0,start});
//처음 문자에서 동일한 문자로 가는 최소 치환 횟수는 0이다.
d[start]=0;
//pq가 empty가 아닐때 까지
while(!pq.empty()){
//해당 노드로 가기 까지 위한 비용값
//pq에 저장시 음수로 바꿔 넣었기 때문에 cost값을 꺼낼 때 -를 붙이고 값을 꺼낸다.
int cost=-pq.top().first;
//현재 노드
int now=pq.top().second;
pq.pop();
//이미 방문한 노드인 경우 생략
if(cost>d[now]){
continue;
}
//각 그래프의 연결된 노드를 확인한다.
for(int i=0;i<graph[now].size();i++){
int c=cost+graph[now][i].second;
if(c<d[graph[now][i].first]){
d[graph[now][i].first]=c;
pq.push({-c,graph[now][i].first});
}
}
}
}
int main(){
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
cin>>a>>b>>n>>m;
fill(d, d+1001, INF);
for(int i=0;i<m;i++){
int s,e;
cin>>s>>e;
//s에서 e로 변겅하는데 걸리는 횟수
//양방향 이다
graph[s].push_back({e,1});
graph[e].push_back({s,1});
}
dijkstar(a);
//치환 가능한 경우
if(d[b]!=INF){
cout<<d[b]<<"\n";
}
//치환 불가능한 경우
else{
cout<<-1<<"\n";
}
return 0;
}
이해가 안되는 부분이 있다면 편하게 댓글 남겨주세요 😊