문제
https://www.acmicpc.net/problem/32197
다익스트라를 살짝 변형하여 풀었다.
문제 설명은 다음과 같다.
지하철의 전기를 공급받는 방식(급전 방식)은 직류와 교류로 구분된다. 열차 운행 중 급전 방식이 바뀌게 되면 잠시 전력 공급이 중단된다. 이러한 현상을 절연이라 부른다. 열차 탑승객의 만족도는 절연이 적게 발생할수록 높아진다.
서울특별시에는 개의 지하철역이 있고, 두 역을 직접 잇는 선로 개가 설치되어 있다. 각 역에는 부터 번까지의 번호가, 선로에는 1부터 번까지의 번호가 붙어있다. 설치되어 있는 선로만으로 임의의 두 역 사이를 이동할 수 있다. 각 선로는 직류 또는 교류 중 하나의 방식으로 전기를 공급하며 양방향으로 통행할 수 있다.
열차는 어떤 역과 이어진 선로를 통해 다른 역으로 이동하는 과정을 몇 번이든 반복할 수 있다. 이 때, 이용하는 선로의 급전 방식이 직류에서 교류로, 또는 교류에서 직류로 바뀐다면 절연이 발생한다.
당신은 열차 기관사이다. 당신은 번 역에서 출발해서, 선로를 통해 번 역까지 열차를 운행하고자 한다. 이 때 절연이 일어나는 횟수를 최소로 하는 경로로 운행할 때, 절연이 몇 번 발생하는지 구해보자.
입력
첫 줄에 지하철역의 수 과 선로의 수 이 정수의 형태로 사이에 공백을 두고 주어진다.
다음 개의 줄에 걸쳐, (1 ≤ i ≤ M)번째 줄에 세 정수 Si, Ei, Ti가 사이에 공백을 두고 주어진다. 이는 i번 선로가 Si번 역과 Ei번 역을 직접 연결하며, Ti=0이라면 직류로, Ti=1이라면 교류로 전기를 공급받음을 나타낸다.
다음 줄에 시작 역과 끝 역을 나타내는 두 정수 A, B가 사이에 공백을 두고 주어진다.
출력
A번 역에서 B번 역까지 열차를 운행할 때 급전 방식이 바뀌는 최소 횟수를 정수의 형태로 출력한다.
풀이
정답 코드는 다음과 같다.
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v[100003];
int n, m, s, e, t, start, dest, dist[100003], cNode, cCost;
void dijkstra(int node){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[node] = 0;
pq.push({node, 0});
while(!pq.empty()){
tie(cNode, cCost) = pq.top();
pq.pop();
for (pair<int,int> i : v[cNode]){
int next = i.first, nCost = i.second;
bool isChange = cCost == nCost ? false : true;
int nDist = isChange ? dist[cNode] + 1 : dist[cNode];
if(dist[next] > nDist){
dist[next] = nDist;
pq.push({next, nCost});
}
}
}
}
int main(){
cin >> n >> m;
fill(&dist[0], &dist[n + 3], 99999999);
for (int i = 0; i < m; i++){
cin >> s >> e >> t;
v[s].push_back({e, t});
v[e].push_back({s, t});
}
cin >> start >> dest;
dijkstra(start);
cout << dist[dest] << '\n';
return 0;
}
일반적인 다익스트라는 (다음 노드의 현재 거리 > 현재까지의 거리 + 다음 노드 까지의 거리) 라면 위 코드에서는 이 방식을 살짝 변형했다.
while(!pq.empty()){
tie(cNode, cCost) = pq.top();
pq.pop();
for (pair<int,int> i : v[cNode]){
int next = i.first, nCost = i.second;
bool isChange = cCost == nCost ? false : true;
int nDist = isChange ? dist[cNode] + 1 : dist[cNode];
if(dist[next] > nDist){
dist[next] = nDist;
pq.push({next, nCost});
}
}
}
현재 전기 공급 상태 = cCost, 다음 전기 공급 상태 = nCost, 다음 절연 발생 횟수 = nDist 이다.
만약 현재 전기 공급 상태와 다음 전기 공급 상태가 같다면 false, 다르다면 true를 준다.
전기 공급 상태가 다르다면 현재 node의 dist값에 1을 더한 값을, 같다면 현재 node의 dist값을 nDist에 저장한다.
이후 다음 노드의 dist값과 비교한다.
방문 배열로 bfs를 하여 최단 거리를 구하는 로직과 유사하다.