[백준 13905] 세부

문제 풀이

 

숭이는 혜빈이를 위해서 금 빼빼로를 최대한으로 들고 가고 싶어 합니다.

그런데 금 빼빼로를 혜빈이까지 옮기기 위해서는 그만큼의 무게를 견디는 다리가 있어야 하는데요.

어떻게 하면 숭이가 혜빈이까지 움직일 수 있는지 구하는 게 이번 문제입니다.

 

우선은 최대한 금 빼빼로를 가져다가 주면 좋아하기 때문에, 최대한으로 설정해놓고 움직일 수 있도록 다리를 만들어야 합니다. 기존에 MST를 이용해서 어떻게 하면 최소한의 비용으로 모든 도시들을 연결한 방법이 있었는데, 이것을 반대로 생각해서 최대한의 비용으로 모든 도시들을 연결하게 설정합니다.

왜냐하면 우리는 금 빼빼로를 최대한으로 들고 가야하기 때문입니다.

 

최대한의 비용으로 그래프를 설계했다면 아래와 같을 것입니다.

노란색으로 색칠한 부분이 우리가 만든 최대의 비용으로 만든 그래프입니다.

이때 숭이가 1번 집에 있고, 혜빈이가 5번 도시에 있을 때 어떻게 하면 최대한 많은 금 빼빼로를 혜빈이에게 줄 수 있을까요?

 

우선은 혜빈이에게 갈려면 빨간색 선으로 되어있는 것처럼 7번 집, 6번 집, 5번 집을 거쳐가야 할 겁니다.

7번 집의 다리 내구도를 보니까 4까지 견딜 수 있고,

6번 집의 다리 내구도를 보니까 4까지 견딜 수 있고,

5번 집의 다리 내구도를 보니까 3까지 견딜 수 있네요.

즉 최대한 많은 금 빼빼로는 총 3개만 가져갈 수 있다는 것을 알았습니다.

4개를 가져가게 되면 6번 집에서 5번 집으로 갈 때 무너지겠죠.

 

어떻게 하면 이렇게 계산할 수 있을까요?

아까 위에서 우리는 MST를 최대 비용으로 집들을 연결했습니다.

1, 7을 연결할 때 두 집을 연결하는 과정에서 우리는 따로 인접 리스트 그래프를 한 개 더 만듭니다.

이 그래프는 얼마큼 금 빼빼로를 가져갈지 계산하기 위해서입니다.

 

그래서 두 그래프를 연결할 때마다 인접 리스트로 두 집의 양방향 연결을 만들어주고,

숭이 내 집에서 혜빈이 집까지 최소한의 비용으로 확인하면서 찾아가면 문제를 해결할 수 있습니다.

 

모든 집 들을 다리로는 나올 수 없는 987654321(무한대)형태로 초기화시킨 후,

숭이 내 집에서 출발해서 인접한 모든 집들을 확인하면서 더 싼 비용으로 갱신해나가면 됩니다.

이렇게 갱신해나가면 위의 빨간색 선분 처럼 우리는 1번 집에서 5번 집으로 갈 때 min(4, 4, 3)을 만나 결국 3이라는 값을 도출할 수 있습니다.

 

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 100001;
const int INF = 987654321;

int N, M, s, e;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];

vector<pair<int, int> > adj[MAX];
bool visit[MAX];
int dist[MAX];

bool compare(const pair<int, pair<int, int> >&  a, const pair<int, pair<int, int> >&  b)
{
	return a.first > b.first;
}

int findParent(int x)
{
	if (x == parent[x]) return x;
	return parent[x] = findParent(parent[x]);
}

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void input()
{
	cin >> N >> M >> s >> e;
	for (int i = 0; i < M; i++)
	{
		int h1, h2, k;
		cin >> h1 >> h2 >> k;
		edges.push_back({ k, {h1,h2} });
	}
}

void kruskal()
{
	sort(edges.begin(), edges.end(), compare);
	for (int i = 1; i <= N; i++) parent[i] = i;

	int sz = static_cast<int>(edges.size());
	vector<int> ans;
	for (int i = 0; i < sz; i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (findParent(a) != findParent(b))
		{
			unionParent(a, b);
			adj[a].emplace_back(b, cost);
			adj[b].emplace_back(a, cost);
		}
	}
}

void dijkstra()
{
	fill(dist, dist + MAX, INF);

	queue<int> q;
	q.push(s);
	visit[s] = true;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (int i = 0; i < adj[cur].size(); i++)
		{
			int next = adj[cur][i].first;
			int nextDistance = adj[cur][i].second;

			if (visit[next]) continue;
			visit[next] = true;
			// 핵심: 금빼빼로를 최대한으로 들고가려고 할 때 그 무게를 견딜 수 있는 걸 찾아야하기 때문에
			// 최소한 무게를 버틸 수 있도록 다리의 무게제한을 갱신한다.
			dist[next] = min(dist[cur], nextDistance);
			q.push(next);
		}
	}

	// 중요한 점은 못갈 수 있다는 것
	if (dist[e] == INF)
		cout << "0\n";
	else
		cout << dist[e] << endl;
}

void solve()
{
	input();
	kruskal();
	dijkstra();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}