BOJ 17270 - 연예인은 힘들어

문제

그래프 상의 두 점 \(v_j, v_s\)가 주어지면, 임의의 점 \(v\)에 대해 두 점과의 최단 경로의 합이 최소가 되는 점들을 찾고, 나머지 쿼리들을 적용시키는 문제이다.

조건 1. 지헌이의 출발 위치와 성하의 출발 위치는 새로운 약속 장소가 될 수 없다.
조건 2. 성품도 훌륭한 지헌이는 새로운 약속 장소는 지헌이가 걸리는 최단 시간과 성하가 걸리는 최단 시간의 합이 최소가 되도록 하고 싶다.
조건 3. 지헌이가 더 늦게 도착하면 성하에게 안좋은 소리를 들을 것이 뻔하기에, 1번과 2번 조건을 만족하는 장소 중에서도 지헌이가 성하보다 늦게 도착하는 곳은 약속 장소가 될 수 없다.
조건 4. 위의 세 조건을 모두 만족하는 약속 장소가 여러 곳이 있다면, 그 중에 지헌이로부터 가장 가까운 곳이 최종 약속 장소가 된다. 그런 장소도 여러 곳이 있다면, 그 중에 번호가 가장 작은 장소가 최종 약속 장소가 된다.

풀이

\(v_j, v_s\)와의 최단 경로는 다익스트라 알고리즘으로 쉽게 구할 수 있다.

조건 1, 2는 다익스트라를 구현하면서 적용되고, 3은 모든 점들에 대한 최단 경로가 필요하기 때문에 다익스트라를 돌린 다음 따로 적용해줘야 한다. 이때 두 점과의 최단 경로를 저장하기 위해 vector<pair<int, int> > res 벡터를 만들었다.
첫 번째 원소는 두 점과의 최단 경로, 두 번째 원소는 해당하는 점의 인덱스이다. 이렇게 생성하고 정렬하면 나중에 4번의 두 번째 조건인 그런 장소도 여러 곳이 있다면, 그 중에 번호가 가장 작은 장소가 최종 약속 장소가 된다.라는 조건을 편하게 처리할 수 있다.

조건 3은 1, 2를 만족하는 장소들 중에서 적용시켜야 하기 때문에, 두 점과의 최단 경로를 구하기 전에 3을 적용시키면 WA를 받는다. 같은 흐름으로, 4에서도 첫 번째 조건을 만족하는 장소를 먼저 찾아본 뒤, 거리가 모두 같다면 번호가 작은 장소를 골라주어야 한다. 이 과정에서 위의 res 벡터를 사용하면 편리하다. 코드를 통해 설명하겠다.

소스코드

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>

using namespace std;
using pii=pair<int, int>;
using vi=vector<int>;
using lld=long long;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int v, m, j, s, cur;
	cin>>v>>m;
	vi ij(v, -1), is(v, -1);
	vector<vi> adj(v, vi(v, -1));
	vector<pii> res;
	for(int i=0;i<m;i++){
		int s, e, w;
		cin>>s>>e>>w;
		if(adj[--s][--e]!=-1 && adj[s][e]<=w) continue;
		adj[s][e]=w;
		adj[e][s]=w;
	}
	cin>>j>>s;
	ij[--j]=0;
	is[--s]=0;
	queue<int> q;
	q.push(j);
	while(!q.empty()){
		cur=q.front();
		q.pop();
		for(int i=0;i<v;i++){
			if(adj[cur][i]!=-1 && (ij[i]==-1 || ij[i]>ij[cur]+adj[cur][i])){
				ij[i]=ij[cur]+adj[cur][i];
				q.push(i);
			}
		}
	}
	q.push(s);
	while(!q.empty()){
		cur=q.front();
		q.pop();
		for(int i=0;i<v;i++){
			if(adj[cur][i]!=-1 && (is[i]==-1 || is[i]>is[cur]+adj[cur][i])){
				is[i]=is[cur]+adj[cur][i];
				q.push(i);
			}
		}
	}
	for(int i=0;i<v;i++){
		if(i==j || i==s) continue;
		res.push_back(make_pair(ij[i]+is[i], i));
	}
	sort(res.begin(), res.end());
	m=10000000;
	for(int i=res.size()-1;i>-1;i--){
		int t=res[i].second;
		if(m>res[i].first) m=res[i].first;
		if(ij[t]>is[t]) res.erase(res.begin()+i);
	}
	for(int i=res.size()-1;i>-1;i--){
		if(res[i].first!=m) res.erase(res.begin()+i);
	}
	if(res.empty()) cout<<-1;
	else{
		int tj=100000000, idx;
		for(int i=0;i<res.size();i++){
			if(tj>ij[res[i].second]){
				tj=ij[res[i].second];
				idx=res[i].second+1;
			}
		}
		cout<<idx;
	}
	return 0;
}

• 61, 62번째 줄이 각각 두 점에서의 최단 경로계산과 조건 3번을 계산하는 코드로, 두 코드의 순서가 바뀌게 되면 위에서 설명한 것처럼 문제가 생긴다.
  최단 경로인 m만 제대로 계산된다면, 2와 3의 조건은 뭐가 먼저 적용되든 상관이 없기 때문에, 62번째 줄에서 3번을 먼저 없앤 후 m 값이 필요한 2번의 조건을 65번째 줄에서 처리했다.
• res를 정렬할 때 pair의 두 번째 값인 인덱스를 기준으로 정렬되었기 때문에, 4번의 두 번째 조건은 첫 번째 조건인 지헌이의 경로의 최솟값을 구하면 자동으로 만족하게 된다.

풀고나서

• sort()를 사용할 때 bool 타입의 함수로 구현해도 된다.(오름차순일 경우 a<b이면 true 리턴)
• 벡터는 fill(v.begin(), v.end(), 0)으로 간단하게 초기화할 수 있음
• 같은 간선에 대해 여러 가중치가 있을 수 있다는 설명이 없어서 헤매었다.