백준 16402번 제국

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

문자열 처리와 유니온 파인드 알고리즘을 이용해야 풀 수 있었던 문제였습니다.

전형적인 유니온 파인드 알고리즘과 달리 집합의 root가 끊임 없이 바뀌기 때문에 parent 배열만 이용해서 집합을 표현했습니다.

제국 간의 전쟁을 할 때 서로 다른 집합에 있는 나라끼리 싸우면 해당 집합의 root 즉, 종주국끼리 전쟁을 합니다.

따라서, 주어진 문자열에 나와있는 그대로 전쟁하는 것이 아니기 때문에 다음과 같이 경우의 수를 나누어야합니다.

i) 속국과 속국의 종주국끼리 전쟁을 할 때

ii) 서로 다른 종주국끼리 전쟁을 할 때

iii) 한 쪽은 종주국이고 다른 한 쪽은 다른 종주국의 속국일 때

사실 ii)와 iii)는 같은 경우라고 봐도 됩니다. 왜냐하면, ii)와 iii) 모두 결과적으로는 종주국끼리 전쟁을 하기 때문입니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <map>

#include <vector>

using namespace std;

 

const int MAX = 500;

 

int N, M;

map<string, int> string2int; //왕국 이름에 인덱스 부여하기 위해

map<int, string> int2string; //인덱스를 통해 왕국 이름을 찾기 위해

int parent[MAX]; //종주국이 누구인지 찾기 위해

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

        string bufferflush;

        getline(cin, bufferflush); //getline 받기 전에 버퍼를 비워줘야한다

 

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

                 parent[i] = i; //우선 모두가 종주국

 

        int idx = 0;

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

        {

                 string s;

                 getline(cin, s);

                 int space = 0;

                 string temp;

 

                 for (int j = 0; j < s.length(); j++)

                 {

                         if (s[j] == ' ')

                         {

                                 space++;

                                 continue;

                         }

                         else if (space == 2)

                         {

                                 temp += s[j]; //왕국 이름은 space가 두번 나온 다음 등장

                         }

                 }

                 string2int[temp] = idx; //인덱스 부여하고

                 int2string[idx++] = temp; //해당 인덱스에 왕국 이름 저장

        }

 

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

        {

                 string s;

                 getline(cin, s);

                 int space = 0;

                 int comma = 0;

                 vector<int> v;

                 string temp;

                 for (int j = 0; j < s.length(); j++)

                 {

                         if (s[j] == ' ')

                         {

                                 space++;

                                 continue;

                         }

                         else if (space == 2)

                         {

                                 //쉼표가 나오면 왕국 이름이 다 나왔다는 뜻

                                 if (s[j] == ',')

                                 {

                                          comma++;

                                          v.push_back(string2int[temp]); //v[0], v[1]에 왕국 이름이 저장

                                          temp.clear();

                                          space = 0;

                                          continue;

                                 }

                                 temp += s[j];

                         }

                         else if (comma == 2)

                         {

                                 //v[0]가 v[1]을 이김

                                 if (s[j] == '1')

                                 {

                                          //v[0]가 v[1]의 속국이였다면 전세 역전

                                          if (parent[v[0]] == v[1])

                                                  parent[v[0]] = v[0];

                                          //v[0]가 v[1]이 다른 집합에 속해 있다면 v[0]와 v[1]의 종주국을 찾는다

                                          if (parent[v[0]] != v[0] && parent[v[0]] != v[1])

                                                  v[0] = parent[v[0]];

                                          if (parent[v[1]] != v[1] && parent[v[1]] != v[0])

                                                  v[1] = parent[v[1]];

 

                                          //v[1]이 졌으므로 v[0]가 v[1]의 종주국

                                          parent[v[1]] = v[0];

                                          //v[1]이 종주국인 속국들의 종주국은 v[0]로 바뀐다

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

                                                  if (parent[i] == v[1])

                                                          parent[i] = v[0];

                                 }

                                 //v[1]이 v[0]를 이김

                                 else

                                 {

                                          if (parent[v[1]] == v[0])

                                                  parent[v[1]] = v[1];

                                          if (parent[v[0]] != v[0] && parent[v[0]] != v[1])

                                                  v[0] = parent[v[0]];

                                          if (parent[v[1]] != v[1] && parent[v[1]] != v[0])

                                                  v[1] = parent[v[1]];

 

                                          parent[v[0]] = v[1];

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

                                                  if (parent[i] == v[0])

                                                          parent[i] = v[1];

                                 }

                         }

                 }

        }

        int cnt = 0;

        vector<string> alpha;

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

                 if (parent[i] == i)

                 {

                         cnt++;

                         alpha.push_back(int2string[i]);

                 }

        cout << cnt << "\n";

        //정렬

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

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

        {

                 cout << "Kingdom of ";

                 cout << alpha[i] << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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