백준 13905 - 세부(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13905

13905번: 세부

최소 스패닝 트리와 DFS를 이용해 풀었습니다.

숭이의 출발위치에서 혜빈이의 위치까지 이동할 때, 숭이가 들고 갈 수 있는 최대 금빼빼로의 개수를 구하는 문제입니다.

들고 갈 수 있는 금빼빼로는 다리를 이동할 때, 해당 다리의 비용만큼만 들고 갈 수 있습니다.
따라서, 집들을 연결할 때, 비용이 작은 것들이 아닌 큰 비용을 가진 다리들로 연결해야 함을 알 수 있습니다.

일단, 모든 집들이 연결되어야 하니 최소 스패닝 트리를 이용해 집들을 연결할 것입니다.
또한, 위에서 말한것과 같이 연결할 때, 비용을 큰 것부터 연결하기 위해 정렬을 큰 값들을 기준으로 해줍니다.

모든 집들을 연결했다면, 숭이의 위치에서 혜빈이의 위치까지를 찾아가야 합니다.
이때, MST를 통해 어떻게 다리들이 연결되었는지를 알고 있습니다.
그렇다면 연결된 다리를 이용해 그래프 탐색을 숭이부터 혜빈이까지 해준다면 길을 찾아갈 수 있을 것입니다.

이때, 최대로 들고 갈 수 있는 뺴빼로를 구해야하니, DFS를 통해서 모든 경우를 확인한 뒤, 최대 빼빼로의 개수를 찾아줍니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

typedef struct info{
	int x;
	int y;
	int cost;
}info;
int N, M;
int s, e;
int max_cnt;
vector<info> connect;
int parent[100001];
int check[100001];
vector<pair<int, int>> line[100001];

void reset_parent(){
	for(int i = 1; i <= N; i++){
		parent[i] = i;
	}
}

bool cmp(info a, info b){
	if(a.cost > b.cost) return true;
	else return false;
}

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

void MST(){
	reset_parent();
	for(int i = 0; i < connect.size(); i++){
		int x = Find(connect[i].x);
		int y = Find(connect[i].y);
		if(x != y){
			parent[x] = y;
			line[connect[i].x].push_back({connect[i].y, connect[i].cost});
			line[connect[i].y].push_back({connect[i].x, connect[i].cost});
		}
	}	
}

void find_max(int x, int cnt){
	check[x] = 1;
	if(x == e){
		max_cnt = max(max_cnt, cnt);
		return;	
	}
	for(int i = 0; i < line[x].size(); i++){
		int xx = line[x][i].first;
		int n_cnt = min(cnt, line[x][i].second);
		if(check[xx] == 0) find_max(xx, n_cnt);
	}
}

void solve(){
	sort(connect.begin(), connect.end(), cmp);
	MST();
	find_max(s, 987654321);
	cout << max_cnt;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	cin >> s >> e;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		connect.push_back({x, y, cost});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.