전국시대
문제 해석
주어진 조건으로 각 기록을 실행시켰을 때, 국가들의 남은 병력 수를 구하는 문제입니다.
M개의 각각의 기록은 다음과 같습니다.
- 동맹 - 두 나라가 서로 동맹을 맺습니다. 두 나라의 병력이 하나로 합쳐집니다.
- 전쟁 - 두 나라가 서로 전쟁을 벌입니다. 병력이 더 많은 나라가 승리하며, 패배한 나라는 속국이 됩니다. 이때 남은 병력 = 승리한 나라 병력의 수 - 패배한 나라 병력의 수 입니다.
설계(5)
문제에서 주어진 기록들을 수행할 때 중요한 점은 각 나라의 동맹과 속국을 체크하는 것입니다.
이를 체크하기 아주 좋은 알고리즘인 Union-find알고리즘을 이용하면 O(M)에 모든 나라 병력을 업데이트할 수 있습니다.
Union-find알고리즘 자체의 시간복잡도는 에커만함수에 의해 거의 O(1)의 시간복잡도이기 때문입니다.
이후 남은 나라를 체크 후 정렬을 하는데 최악의 경우 O(NlogN)의 시간복잡도가 소모됩니다.
따라서, 총 시간복잡도는 O(M+NlogN)정도로 시간안에 구현이 가능할 것으로 보입니다.
각 기록은 두개의 모드가 존재하는데 두 경우 모두 마찬가지로 cost가 높은 나라를 부모로 둔다고 생각하면 구현이 편해집니다.
모드에 따라서 cost를 더해주느냐 빼주느냐 차이만 있을 뿐입니다.
구현(10)
코드
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100000
int par[MAXN];
int cost[MAXN];
bool visited[MAXN];
int N, M;
vector<int> ans;
int Find(int x) {
if (par[x] == -1) return x;
return par[x] = Find(par[x]);
}
void Merge(int u, int v, int mode) {
u = Find(u);
v = Find(v);
if (u == v) return;
if (mode == 1) {
if (cost[u] > cost[v]) {
par[v] = u;
cost[u] += cost[v];
cost[v] = 0;
}
else {
par[u] = v;
cost[v] += cost[u];
cost[u] = 0;
}
}
else {
if (cost[u] > cost[v]) {
par[v] = u;
cost[u] = cost[u] - cost[v];
cost[v] = 0;
}
else {
par[u] = v;
cost[v] = cost[v] - cost[u];
cost[u] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
memset(par, -1, sizeof(par));
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> cost[i];
}
while (M--) {
int mode, u, v;
cin >> mode >> u >> v;
u--;
v--;
Merge(u, v, mode);
}
for (int i = 0; i < N; i++) {
int cur = Find(i);
if (visited[cur] || cost[cur]==0) continue;
visited[cur] = true;
ans.push_back(cost[cur]);
}
sort(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
디버깅
제출결과
24 ms
마무리
Union-find 알고리즘을 활용한 문제였습니다.
해당 알고리즘에 대한 이해도가 있다면 쉽게 구현이 가능할 것입니다.