백준 23743 - 방탈출(C++)

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

23743번: 방탈출

최소 스패닝 트리를 이용한 문제입니다.

워프와 비상탈출구를 설치해 모든 친구들이 탈출하려고 할 때 걸리는 최소 시간을 구하는 문제입니다.

워프는 방을 잇는 역할이며, 비상탈출구는 설치된 방에서 밖으로 탈출할 수 있도록 해줍니다.
따라서, 워프와 방을 적절히 사용해 탈출해야 합니다.

이 문제릂 푸는 방법은 간단합니다.
탈출한다고 했으니, 탈출하는 곳을 하나 만들어 N+1개의 방을 연결하도록 해주기만 하면 됩니다.
최소 스패닝 트리를 통해 만든다면, 최소 비용으로 탈출하는 곳까지 연결할 수 있으므로 한번에 구할 수 있게 됩니다.

저는 탈출하는 곳을 ’0번 방‘으로 정한 뒤, 비상탈출구들을 X번과 0번 방이 연결되는 것처럼 만들어 줬습니다.


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

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

using namespace std;

int N, M;
typedef struct info{
	int x;
	int y;
	int cost;
}info;
vector<info> connect;
int parent[200001];

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 solve(){
	reset_parent();
	sort(connect.begin(), connect.end(), cmp);
	int cost = 0;
	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;
			cost += connect[i].cost;
		}
	}
	cout << cost;
}

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

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