백준 9370번 미확인 도착지

🔒[문제 url]

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

🔑알고리즘

다익스트라 문제이다.
$g$와 $h$의 교차로($\vec{gh}$)를 지난 경로는 최단경로여야하므로,
(출발점에서 목적지에 가는 최단경로의 길이) = (출발점에서 $\vec{gh}$를 지나 목적지에 가는 최단경로의 길이) 이어야한다.

• $\vec{gh}$를 지나는 경로의 경우는 다음과같다.

1. (출발점) $\to$ $g$ $\to$ $h$ $\to$ (목적지)
2. (출발점) $\to$ $h$ $\to$ $g$ $\to$ (목적지)

• 즉, 출발점에서 목적지에 가는 최단경로의 길이를 구해둔 뒤 다음과같이 작업한다.
  1. 출발점에서 $g$까지의 최단경로를 구한다.
  2. 출발점에서 $h$까지의 최단경로를 구한다.
  3. $g$에서 목적지까지의 최단경로를 구한다.
  4. $h$에서 목적지까지의 최단경로를 구한다.
     
     
  • (1 + $\vec{gh}$ + 3)의 길이와 미리 구해둔 출발점에서 목적지에 가는 최단경로의 길이가 동일하면 가능한 후보이다.
  • (2 + $\vec{gh}$ + 4)의 길이와 미리 구해둔 출발점에서 목적지에 가는 최단경로의 길이가 동일하면 가능한 후보이다.
  • 이를 위해 $\vec{gh}$의 거리를 -1로 설정하여 여러 번 건너는 것을 방지한다.
    
    
• 중복 제거와 오름차순 출력을 동시에 해결하기 위해 set 자료구조를 활용해 답안을 출력한다.

🐾부분 코드

void Init()
{
	for(int i = 1; i <= 2000; i++) graph[i].clear();
}

<초기화 함수>
테스트 케이스마다 그래프를 초기화해준다.

int Disconnect()
{
	int rtn;
	for(int i = 0; i < graph[g].size(); i++)
		if(graph[g][i].first == h)
			rtn = graph[g][i].second,
			graph[g][i].second = -1;
	for(int i = 0; i < graph[h].size(); i++)
		if(graph[h][i].first == g)
			graph[h][i].second = -1;
	return rtn;
}

<$\vec{gh}$의 길이 -1로 설정>
중복 교차를 방지하기 위해 -1로 설정하고, 기존 교차로의 길이를 반환한다.

void ijk(int start)
{
	fill(dist+1,dist+n+1,2e9);
	priority_queue<pii> pq;
	pq.push({0,start});
	dist[start] = 0;

	while(!pq.empty())
	{
		int now = pq.top().second;
		int d1 = -pq.top().first;
		pq.pop();

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i].first;
			int d2 = graph[now][i].second;
            //최단경로를 구해둔 후에는 gh 교차로는 건너지 않음
			if(d2 == -1) continue;

			if(dist[next] > d1 + d2)
			{
				dist[next] = d1+d2;
				pq.push({ -(d1+d2), next });
			}
		}
	}

}

<다익스트라 함수>
출발지에서 목적지까지의 최단경로를 구했두었다면, $\vec{gh}$를 -1로 설정해두었기때문에 건너지 않는다.

void SOLVE()
{
	while(tc--)
	{
		Init();

		//Input
		cin >> n >> m >> t;
		cin >> s >> g >> h;
		for(int i = 0; i < m; i++)
		{
			int a,b,d; cin >> a >> b >> d;
			graph[a].emplace_back(b,d);
			graph[b].emplace_back(a,d);
		}
		for(int i = 0; i < t; i++) cin >> candi[i];

		//Solve
		ijk(s);
		int toG = dist[g];
		int toH = dist[h];
		for(int i = 1; i <= n; i++) origin[i] = dist[i];

		//g-h 경로 차단
		int connect = Disconnect();

		set<int> ans;
		ijk(g);
		for(int i = 0; i < t; i++)
			if(dist[candi[i]] != 2e9)
				if(origin[candi[i]] == toH + connect + dist[candi[i]])
					ans.insert(candi[i]);
		ijk(h);
		for(int i = 0; i < t; i++)
			if(dist[candi[i]] != 2e9)
				if(origin[candi[i]] == toG + connect + dist[candi[i]])
					ans.insert(candi[i]);

		//Output
		set<int>::iterator it;
		for(it = ans.begin(); it != ans.end(); it++)
			cout << *it << " ";
		cout << '\n';
	}

}

<전체 알고리즘 반복>
(초기화 - 입력 - 최단경로 구하기 - 경로차단 - 길이 비교 - 출력) 을 테스트케이스만큼 반복한다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int tc,n,m,t;
int s,g,h;
typedef pair<int,int> pii;
vector<pii> graph[2001];
int candi[101];//목적지 후보

int origin[2001];//최단 경로
int dist[2001];//g h를 반드시 지나는 최단 경로


void INPUT()
{
	IAMFAST
	cin >> tc;
}

void Init()
{
	for(int i = 1; i <= 2000; i++) graph[i].clear();
}

int Disconnect()
{
	int rtn;
	for(int i = 0; i < graph[g].size(); i++)
		if(graph[g][i].first == h)
			rtn = graph[g][i].second,
			graph[g][i].second = -1;
	for(int i = 0; i < graph[h].size(); i++)
		if(graph[h][i].first == g)
			graph[h][i].second = -1;
	return rtn;
}

void ijk(int start)
{
	fill(dist+1,dist+n+1,2e9);
	priority_queue<pii> pq;
	pq.push({0,start});
	dist[start] = 0;

	while(!pq.empty())
	{
		int now = pq.top().second;
		int d1 = -pq.top().first;
		pq.pop();

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i].first;
			int d2 = graph[now][i].second;
			if(d2 == -1) continue;

			if(dist[next] > d1 + d2)
			{
				dist[next] = d1+d2;
				pq.push({ -(d1+d2), next });
			}
		}
	}

}

void SOLVE()
{
	while(tc--)
	{
		Init();

		//Input
		cin >> n >> m >> t;
		cin >> s >> g >> h;
		for(int i = 0; i < m; i++)
		{
			int a,b,d; cin >> a >> b >> d;
			graph[a].emplace_back(b,d);
			graph[b].emplace_back(a,d);
		}
		for(int i = 0; i < t; i++) cin >> candi[i];

		//Solve
		ijk(s);
		int toG = dist[g];
		int toH = dist[h];
		for(int i = 1; i <= n; i++) origin[i] = dist[i];

		//g-h 경로 차단
		int connect = Disconnect();

		set<int> ans;
		ijk(g);
		for(int i = 0; i < t; i++)
			if(dist[candi[i]] != 2e9)
				if(origin[candi[i]] == toH + connect + dist[candi[i]])
					ans.insert(candi[i]);
		ijk(h);
		for(int i = 0; i < t; i++)
			if(dist[candi[i]] != 2e9)
				if(origin[candi[i]] == toG + connect + dist[candi[i]])
					ans.insert(candi[i]);

		//Output
		set<int>::iterator it;
		for(it = ans.begin(); it != ans.end(); it++)
			cout << *it << " ";
		cout << '\n';
	}

}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

음.. 살짝 고평가된 느낌이 들었다. Dijkstra 문제의 유형은 좀 뻔해서 어느정도까지는 문제를 꼬아놓더라고 아이디어를 쉽게 찾을 수 있는 것같다.
물론 다익스트라를 최근에 입문해서.. 굼벵이 앞에서 주름잡는 꼴이긴하다..😅