[BOJ/Gold 3] 백준 23743 방탈출(C++)

문제 링크

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

23743번: 방탈출

 

문제

원빈이는 친구들과 함께 방탈출 카페에 갔다. 방탈출 카페에는 1번부터 N번까지 총 N개의 방이 있고, 각 방에는 친구들이 한 명씩 들어가 있다. 모든 방은 외부로부터 완전히 독립되어 있다.

방에서 탈출하지 못하는 친구들이 답답했던 원빈이는 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하려고 한다. 워프는 최대 M개까지 설치할 수 있는데, i번째 워프는 설치하는 데 ci의 시간이 걸리고, 워프를 설치하면 ai번 방과 bi번 방 사이를 이동할 수 있다. 또한 각 방에는 출구로 바로 연결되는 비상탈출구를 설치할 수 있는데, i번 방에 비상탈출구를 설치하는 데 걸리는 시간은 ti이다.

안타깝게도 원빈이는 머리가 나빠 워프나 비상탈출구의 설치 작업을 동시에 여럿 진행할 수 없다. 즉 한 작업이 끝나고 나서야 다음 작업을 이어서 시작할 수 있다.

원빈이를 도와 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 구해보자.

입력

첫 번째 줄에는 방의 개수 N과 설치할 수 있는 워프의 개수 M이 주어진다. (2≤N≤200000, 1≤M≤100000)

다음 M개의 줄에는 워프의 정보를 나타내는 세 정수 ai, bi, ci가 공백으로 구분되어 주어지는데, 이는 ai번 방과 bi번 방 사이를 잇는 워프를 설치하는 데 걸리는 시간이 ci라는 의미이다. 같은 두 개의 방을 잇는 워프가 여러 개 존재할 수 있다. (1≤ai,bi≤N, 1≤ci≤10^4, ai≠bi)

마지막 줄에는 N개의 정수 t1, ..., tn이 주어지는데, ti는 i번째 방에 비상탈출구를 설치하는 데 드는 시간을 의미한다. (1≤ti≤10^4)

출력

모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 출력한다.

예제 입력 1

3 3
1 2 2
2 3 2
3 1 2
3 3 3

예제 출력 1

7

예제 입력 2

3 1
1 2 2
3 3 3

예제 출력 2

8

알고리즘 분류

• 크루스칼 알고리즘

풀이

방 밖을 0이라고 하고, M개의 워프는 A를 시작점, B를 도착점으로 하고 가중치를 C로 하는 간선으로 만든다. 그리고 N개의 비상탈출구는 0을 시작점 ,i을 도착점으로 하고 가중치를 T로 하는 간선으로 만든다.

작업이 끝났다면 최소 스패닝 트리를 만들고, 가중치의 최솟값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 200001
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Start, End, Cost;
};

int N, M;
vector<INFO> Edge;
int Parent[MAX];
LL answer = 0;

void Init() {
	for (int i = 0; i <= N; i++) {
		Parent[i] = i;
	}
}

bool Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

bool isConnected() {
	for (int i = 1; i <= N; i++) {
		if (Find(i) != Find(0)) {
			return false;
		}
	}
	return true;
}

void Input() {
	cin >> N >> M;
	Init();
	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		Edge.push_back({ A,B,C });
	}
	for (int i = 1; i <= N; i++) {
		int T;
		cin >> T;
		Edge.push_back({ 0,i,T });
	}
}

void Settings() {
	sort(Edge.begin(), Edge.end(), Comp);
	for (int i = 0; i < Edge.size(); i++) {
		int S = Edge[i].Start;
		int E = Edge[i].End;
		int C = Edge[i].Cost;
		if (Find(S) != Find(E)) {
			Union(S, E);
			answer += C;
		}
	}
}

void Find_Answer() {
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}