[C++] 백준 23743번: 방탈출

문제 링크

23743번: 방탈출

문제 요약

방을 탈출해야 하는데, 워프와 비상탈출구를 설치할 수 있다. 워프는 각 방 사이를 연결할 수 있고, 비상탈출구는 출구와 방을 직접 연결한다. 모든 방의 사람이 탈출할 수 있도록 비상탈출구와 워프를 설치하는 최소비용을 구해야 한다.

접근 방법

물대기 문제와 완전히 같은 문제라고 생각합니다. 입력의 크기는 이 문제가 조금 더 크긴 하지만, 동일한 접근 방법으로 풀었을 때, 모두 제한 시간 안에 통과합니다.

출구를 가상의 0번 정점으로 생각합니다. 그러면 출구와 방 사이는 비상탈출구를 설치하는 비용의 가중치를 지닌 가상의 간선으로 연결된 상태라고 볼 수 있습니다. 이때, 0번 정점도 포함한 MST를 구하면 됩니다. MST는 크루스칼 알고리즘을 통해서 구했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Edge {
	int v1, v2, w;
	bool operator<(const Edge& a) { return w < a.w; }
};

const int MAX = 301;
int parent[MAX];
vector<Edge> edges;

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

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	int n;
	cin >> n;

	for (int i = 0; i <= n; i++) parent[i] = i;

	for (int i = 1; i <= n; i++) {
		int w;
		cin >> w;
		edges.push_back({ 0, i, w });
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w;
			cin >> w;
			
			if (i == j)
				continue;

			edges.push_back({ i, j, w });
		}
	}

	sort(edges.begin(), edges.end());

	int ans = 0;
	for (auto& i : edges) {
		if (Find(i.v1) != Find(i.v2)) {
			ans += i.w;
			Union(i.v1, i.v2);
		}
	}

	cout << ans << '\n';
	return 0;
}