[백준 15809] 전국시대 (C++)

문제 링크: www.acmicpc.net/problem/15809

15809번: 전국시대

1. 주의할 점

- 동맹 처리를 어떻게 할 것인가?

- 전쟁 처리를 어떻게 할 것인가? 빠트린 조건은 없는가

 

2. 구현

- 동맹 처리: 공통조상 설정 + 공통조상으로 병력합친다

- 전쟁 처리: 병력 감소 + 한 국가 멸망 + 속국 처리(이 부분을 까먹기 쉽다)

- Par[] 배열을 통해 자신의 조상을 나타낸다

- Power[] 배열을 통해 한 나라/국가의 병력을 나타낸다

- Find_p() 함수를 통해 자신의 조상을 찾기 + 조상 갱신 작업 수행

- Make_union() 함수를 통해 동맹 처리

- 전쟁인 경우, 두 국가의 병력 비교한다

- 같을 경우, 두 나라를 멸망 처리한다 -> 두 국가의 병력: 0 & 두 국가의 조상 국가 = 0으로 설정(멸망 표시)

- 한쪽이 클 경우, 병력 감소 + 멸망 처리 + 속국 처리한다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int par[100001];
int power[100001];

int find_p(int x){
    if(par[x]==x) return x;
    return par[x] = find_p(par[x]);
}

void make_union(int a,int b){
    int pa = find_p(a);
    int pb = find_p(b);
    //한쪽으로 병력 합치기 + 동맹 처리
    if(pa<pb){
        par[pb] = pa;
        power[pa]+=power[pb];
        power[pb]=0;
    } 
    else if(pa>pb){
        par[pa] = pb;
        power[pb]+=power[pa];
        power[pa]=0;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int node,edge,a,b,c;
    cin >> node >> edge;
    for(int i=1;i<=node;i++){
        cin >> power[i];
        par[i]=i;   
    }
    for(int i=0;i<edge;i++){
        cin>>a>>b>>c;
        if(a==1)       //동맹
            make_union(b,c);
        else{       //전쟁
            int pb = find_p(b);
            int pc = find_p(c);
            int vb = power[pb];
            int vc = power[pc];
            if(vb==vc){     //멸망
                power[pb]=0;
                power[pc]=0;
                par[pb]=0;
                par[pc]=0;
            }
            //한 국가 멸망+병력 감소+속국 처리
            else if(vb>vc){    
                power[pb]-=vc;		//병력 감소
                power[pc]=0;		//국가 멸망
                par[pc] = pb;		//속국 처리
            }
            else {
                power[pb]=0;
                power[pc]-=vb;
                par[pb] = pc;
            }
        }
    }
    vector<int> v;
    for(int i=1;i<=node;i++){
        if(power[i]!=0)
            v.push_back(power[i]);
    }
    sort(v.begin(),v.end());
    
    cout<<v.size()<<'\n';
    for(int i=0;i<v.size();i++)
        cout << v[i]<<" ";
    return 0;
}