[25.03.10] ps study 백준 16402 제국 리뷰(c++)

luke  · 

백준 16402 제국

16402 문제 바로가기

문제 소개

  1. 문자열 id를 가진 왕국들이 입력으로 들어옴
  2. 전쟁의 결과가 입력으로 들어옴
  3. 전쟁에서 승리할 경우 패배한 왕국과 왕국의 속국들을 전부 속국으로 삼음
  4. 자신의 종주국을 공격하는 경우 속국이 승리하면 종주국과 그 속국들을 속국으로 삼게 됨

아이디어

unordered_map<string,string> parent 자료구조로 분리 집합을 합쳐 주종관계를 나타낸다. ex: c국이 a국을 승리한 경우 a국의 부모는 c국이 되게끔 parent.a='c' 출력은 key value쌍이 같은 국가들을 출력하면 된다.

시간 내 못푼 이유

속국은 기본적으로 다른 왕국을 공격할 수 없지만, 한 가지 예외가 있다. 바로 자신의 종주국을 공격하는 것이다. 만약 이 전쟁에서 속국이 승리한다면 속국 신세에서 벗어나 종주국이었던 왕국과 그 속국들을 속국으로 삼게 된다. 그러나 종주국이 승리한다면 아쉽게도 아무 일도 일어나지 않는다.

해당 조건을 체크하지 않아 두번째 TC가 잘못 나왔고, 원인을 발견하는데 오래걸렸다. 이 부분이 문제의 킥이었다. 분리집합을 합칠 때 만약 전쟁을 하는 두 나라의 부모가 같으면, 진 나라의 부모는 이긴 나라의 부모가 아닌 이긴 나라 가 돼야한다. 이긴 나라의 부모와는 여전히 종주관계가 지속되기 때문이다.

종주국이었던 왕국과 그 속국들을 속국으로 삼게 된다.

제출한 코드

#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;

struct UnionFind
{
    unordered_map<string, string> parent;
    string &find(const string &x)
    {
        if (parent.find(x) == parent.end())
            parent[x] = x;

        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void merge(const string &a, const string &b)
    {
        string rootA = find(a);
        string rootB = find(b);
        parent[rootB] = rootA;
    }
    void merge2(const string &a, const string &b)
    {
        string rootA = find(a);
        string rootB = find(b);
        parent[a] = a;
        parent[rootB] = a;
    }
} uf;

int main()
{
    cin >> n >> m;
    cin.ignore();
    for (int i = 0; i < n; i++)
    {
        getline(cin, s);
        string name = "";
        for (int j = 11; j < s.size(); j++)
            name += s[j];

        if (name != "")
            uf.find(name);
    }
    while (m--)
    {
        getline(cin, s);
        int pv = 11;
        string left = "", right = "";
        while (true)
        {
            if (s[pv] == ',')
            {
                pv++;
                break;
            }
            left += s[pv++];
        }
        pv += 11;
        while (true)
        {
            if (s[pv] == ',')
            {
                pv++;
                break;
            }
            right += s[pv++];
        }
        char winner = s[pv];

        if (uf.find(left) != uf.find(right))
        {
            if (winner == '1')
                uf.merge(left, right);
            else
                uf.merge(right, left);
        }
        else
        {
            if (winner == '1')
                uf.merge2(left, right);
            else
                uf.merge2(right, left);
        }
    }
    vector<string> res;
    for (const auto &iter : uf.parent)
    {
        if (iter.first == iter.second)
            res.push_back(iter.second);
    }
    sort(res.begin(), res.end());
    cout << res.size() << "\n";
    for (string val : res)
        cout << "Kingdom of " << val << "\n";
}

코드 약간의 설명

구조체에 union find에서 쓰일 변수와 함수를 묶었다. 문자열 파싱이 귀찮긴하지만 Kingdom of 문자열의 개수가 11개인 게 불변이기 때문에 split 함수를 만들지 않고 포인터를 옮겨가며 파싱했다. 결과부는 다음 순서로 구현했다.

  1. map의 iterator를 이용하여 순회하며 부모가 같은 왕국 이름을 res vector에 삽입
  2. res vector 정렬
  3. res vector 크기 출력
  4. res vector 하나씩 출력