백준 14496 그대, 그머가 되어

hyoJeong·2021년 6월 1일
0

이번에 포스팅할 문제는
앞에서 다뤘던, 다익스트라 알고리즘을 활용해 푸는 문제입니다.
문제 주소: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;
}

이해가 안되는 부분이 있다면 편하게 댓글 남겨주세요 😊

0개의 댓글