백준 BOJ 2021 - 최소 환승 경로

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

2021번: 최소 환승 경로

디스코드방에서 추천받아서 풀어본 문제

일단 "최소" 라는 단어에서 다익스트라라는 감을 잡았다.

근데 같은 노선끼리는 이동거리를 0으로 해석해줄 수가 있어서,

사실상 같은 노선을 싹 뭉뚱그려서 하나의 무언가로 봐주는 과정이 필요하다

유니온 파인드 비슷한 느낌으로

노선 L개를 N+1번부터 각 노선당 한개의 노드를 할당해줬고,

각 역에서는 갈수있는 노선들을 이어줬다.

 

즉 내가 짠 소스코드 내에서의 이동순서는

[역1 - 노선1 - 역2 - 노선2 - 역3....] 순으로 역과 노선을 번갈아서 이동하게 된다.

이렇게 이동할 때, 역 1에서 역 3으로 가는 환승횟수는 역2에서 노선을 바꾸는 1회로,

 

이를 일반화 해보면

N개의 노선에 올라탔다면

노선에서 다른 노선으로 환승하는 횟수는 N-1번이 되므로

노선에 올라탄 경우의 가중치를 1로, 나머지를 0으로 두었을때의 최단거리를 재고

출력시에 1을 빼주는 방법으로 정답을 구했다.

 

이때, 시작점 S와 E가 서로 동일한 역인 경우 -1을 출력할 수 있으므로

이부분을 따로 처리해주도록 하자.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<int> g[234567];

vector<int> group[123456];
int dist[234567];
int N,L,k;

void dijkstra(int s){
	for(int i=0; i<234567; i++) dist[i] = 998244353;
	priority_queue<pair<int,int>> pq;
	
	dist[s] = 0;
	pq.push({0,s});
	
	while(!pq.empty()){
		int now =  pq.top().y;
		int dis = -pq.top().x;
		pq.pop();
		
		for(auto nxt : g[now]){
			if(nxt > N){
				if(dist[nxt] > dis+1){
					dist[nxt] = dis+1;
					pq.push({-dist[nxt], nxt});
				}
			}
			else{ 
				if(dist[nxt] > dis){
					dist[nxt] = dis;
					pq.push({-dist[nxt], nxt});
				}
			}
		}
	}
	return;
}

int main(){
	int s,e;
	
	cin >> N >> L;
	for(int i=N+1; i<N+L+1; i++){
		while(1){
			cin >> k;
			if(k==-1) break;
			
			g[k].push_back(i);
			g[i].push_back(k);
		}
	}
	cin >> s >> e;
	
	if(s==e){ cout << 0; return 0; }
	
	dijkstra(s);
	
	if(dist[e] == 998244353) cout << -1;
	else cout << dist[e]-1;
	return 0;
}