백준 15809번 전국시대

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

유니온 파인드(Union Find)를 적절히 이용하면 되는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 동맹을 맺을 경우에는 집합의 크기를 더해주고, 전쟁을 할 때에는 집합의 크기를 빼줍니다.

2. 출력할 때는 남아있는 제국의 병사의 수를 정렬해서 출력해줍니다.

#include <iostream>

#include <string>

#include <map>

#include <vector>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000 + 1;

 

int F;

int parent[MAX], setSize[MAX];

 

//루트 찾는 함수

int findParent(int node)

{

        //현재 노드가 집합의 루트라면

        //자신이 속한 집합을 찾았으므로 node 반환

        if (node == parent[node])

                 return node;

 

        //현재 노드가 집합의 루트가 아니라면

        //노드의 루트에 대해 재귀 호출하면서 parent[node] 업데이트

        return parent[node] = findParent(parent[node]);

}

 

//집합을 합치는 함수

void merge(int node1, int node2, int op)

{

        node1 = findParent(node1); //node1이 속한 집합을 찾음

        node2 = findParent(node2); //node2가 속한 집합을 찾음

                                                             //같은 집합이 아닐 경우에만 합친다

        if (node1 != node2)

        {

                 //크기가 더 큰 집합으로 작은 집합이 들어감

                 if (setSize[node1] < setSize[node2])

                         swap(node1, node2);

 

                 parent[node2] = node1; //node2 집합이 node1에 합쳐짐

                 if (op == 1)

                         setSize[node1] += setSize[node2];

                 else

                         setSize[node1] -= setSize[node2];

                 setSize[node2] = 0; //node2가 node1에 흡수되므로

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        for (int i = 1; i <= N; i++)

        {

                 int troop;

                 cin >> troop;

 

                 parent[i] = i;

                 setSize[i] = troop;

        }

 

        for (int i = 0; i < M; i++)

        {

                 int op, country1, country2;

                 cin >> op >> country1 >> country2;

       

                 merge(country1, country2, op);

        }

 

        vector<int> result;

        for (int i = 1; i <= N; i++)

                 if (setSize[i] > 0)

                         result.push_back(setSize[i]);

 

        cout << result.size() << "\n";

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

        for (int i = 0; i < result.size(); i++)

                 cout << result[i] << " ";

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~