백준 Gold 2 제국

제국 (백준 Gold 2)

https://www.acmicpc.net/problem/16402

왕국과 전쟁 결과의 개수가 주어진다

왕국의 각 나라이름 N개와
전쟁결과 M개가 주어질 때
전쟁이 끝났을때, 왕국의 이름을 가진 나라의 개수와
그 나라들의 이름을 오름차순으로 출력하는 문제

풀이 방법

• 각 나라를 pair<int,string>로 관리
  
  • int : 부모 인덱스
    
  • string : 자신의 이름
    
  • 추가적으로 전쟁 결과를 판별하기 위해
    이를 거꾸로 저장한 unordered_map을 사용
    
• 각 나라의 전쟁 결과를 기반으로 Union 시도
  
  • Union 성공 시, 서로 다른 종주국을 가진 나라였다는 뜻이므로
    처리 완료
    
  • Union 실패 시, 동맹 내의 전쟁이므로
    성공한 부모를 따르도록 수정
    
• 마지막에 ‘왕국’의 이름을 체크할때
  FindParent를 사용하여 실제 부모를 ‘재갱신’하는 과정이 필요!
  

제출 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<unordered_map>

using namespace std;

int FindParent(vector<pair<int, string>>& pv, int x)
{
	if (pv[x].first == x)
		return x;

	return pv[x].first = FindParent(pv, pv[x].first);
}

bool Union(vector<pair<int, string>>& pv, int a, int b)
{
	a = FindParent(pv, a);
	b = FindParent(pv, b);
	if (a == b)
		return false;

	pv[a].first = b;

	return true;
}

const string ks = "Kingdom of ";

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<pair<int,string>> pv(n);
	unordered_map<string, int> um;
	
	for (int i = 0; i < n; i++)
	{
		pv[i].first = i;

		string str1,str2,str3;
		cin >> str1 >> str2 >> str3;
		
		pv[i].second = str3;
		um[str3] = i;
	}

	for (int i = 0; i < m; i++)
	{
		string str1, str2, str3, str4, str5;
		cin >> str1 >> str2 >> str3 >> str4 >> str5;

		char c = ',';
		size_t p1 = str3.find(c);
		size_t p2 = str5.find(c);
		string a(str3.begin(), str3.begin() + p1);
		string b(str5.begin(), str5.begin() + p2);

		char ret = str5.back();

		int a1 = um[a];
		int b1 = um[b];

		if (ret == '1')
		{
			if (Union(pv, b1, a1) == false)
			{
				pv[b1].first = a1;
				pv[a1].first = a1;
			}
		}
		else
		{
			if (Union(pv, a1, b1) == false)
			{
				pv[a1].first = b1;
				pv[b1].first = b1;
			}
		}
	}

	vector<string> results;

	for (int i = 0; i < n; i++)
	{
		if (FindParent(pv,i) == i)
		{
			results.push_back(ks + pv[i].second);
		}
	}

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

	cout << results.size() << '\n';

	for (auto& s : results)
	{
		cout << s << '\n';
	}
	return 0;
}

결과

• 사실 문자열 파싱 부분에서 꽤 해매었다
  
  • find + 문자열 생성 부분 대신
    strtok를 사용하여 파싱을 하였는데
    해당 부분이 문제가 되었다
    

strtok

• 일단 strtok를 사용할때
  다음과 같이 사용한 부분이 문제가 되었다
  

char c = ',';
strtok((char*)str.c_str(), &c);

• 나는 내부적으로 안전한 연산인줄 알았기에
  암묵적인 const cast를 사용하였으나
  실제로는 ‘토큰 분리’를 위해 내부 문자열을 수정
  (구분자를 ‘\0’(널문자)로 바꿈)
  
  • 잠재적으로 UB를 일으킬 수 있음
    
• 또한 c가 단순한 문자 하나 이기에
  2번째 인자에서 널문자가 들어있지 않기에
  역시 내부에서 문제로 작동할 가능성이 있음
  
  • 기본적으로 ‘\0’을 확인하여 ‘종료’하는 로직이 기반이므로
    

전반적으로 C 스타일에 가까운 문자열 함수이기에
기본적으로 권장되지 않는 방식이라 한다

대체기능들

• find + substr/find/erase 등
  

  특정 위치를 찾은 후, 그 인덱스를 기반으로
  문자열을 추출하거나 수정하는 방식
  

• stringstream
  

  string 을 문단마다 나눠 읽을때 유용한 기능
  한 line을 읽은 후, 공백마다 분열이 가능!
  

  • getline 기능을 사용하여 token 구분도 가능함
    

#include <sstream>

string line = "Kingdom of Gondor";

istringstream iss(line);

string a, b, c;
iss >> a >> b >> c;

// a = "Kingdom"
// b = "of"
// c = "Gondor"

--------

#include <sstream>

string s = "A,B,C";

istringstream iss(s);

string token;
while (getline(iss, token, ',')) {
    // token: "A", "B", "C"
}