백준 16402번. 제국(c++) / 문자열 처리+유니온파인드

문자열 처리와 유니온파인드를 모두 활용해야 하는 아주 괜찮은 문제이다.

 

글쓴이는 총 2가지 경우로 나누어서 처리해주었다.

1) 속국이 종주국을 공격하는 경우

2) 왕국이 다른 왕국이나 다른 왕국의 속국을 공격하는 경우

 

문제를 풀면서 생각했던 풀이방법을 아래 사진으로 첨부했다. (유니온파인드)

 

문제를 풀면서 또 헤맸던 부분이 문자열 처리 부분이다.

글쓴이는 getline()을 사용하여 문자열 한 줄을 전체 받았는데,

 

이상하게 앞에서 cin으로 n, m을 받고 나서 한 줄의 여백이 자꾸 생기는 바람에

마지막 입력 한 줄을 못받는 이상한 상황?이 벌어졌다. 아마 getline이 '\n'을 인식해서 벌어진 일 같은데,,,, 정확한 이유는 모르겠다,,,

 

그래서 해결 방법을 모색하다 cin.ignore()라는 것을 발견해서 넣어주었다...^^

 

 

코드 첨부

// 제국
#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
int n, m;
string s;
vector<string> nation;
int connect[502] = {0, };
map<string, int> M;
vector<string> final;
 
int find(int a){
   if(a==connect[a]){
       return a;
   }else{
       return connect[a] = find(connect[a]);
   }
}
 
void war(string a, string b) // a가 b를 이겼다.
{
    int x = find(M[a]);
    int y = find(M[b]);
 
    if(x!=y){ // 다른 왕국끼리 싸움 y->x
        connect[y] = x;
    }else{ // 같은 왕국 안에서의 싸움
        connect[M[a]] = M[a];
        connect[x] = M[a];
    }
}
 
int main()
{
    cin>>n>>m;
    cin.ignore();
    for(int i=0; i<n; i++){
        getline(cin, s);
        stringstream ss(s);
        string temp;
        while(ss >> temp){ }
        nation.push_back(temp);
        M[temp] = i;
        connect[i] = i;
    }
 
    for(int i=0; i<m; i++){
        getline(cin, s);
        string a, b;
        int win = s[s.size()-1]-'0';
        int idx = 11;
        while(s[idx]!=','){
            a += s[idx++];
        }
        idx += 12;
        while(s[idx]!=','){
            b += s[idx++];
        }
 
        if(win==1){
            war(a, b);
        }else if(win==2){
            war(b, a);
        }
    }
 
    map<int, int> check;
    for(int i=0; i<n; i++){
        int temp = find(i);
        if(check.count(temp)==0){
            check[temp] = 1;
            final.push_back(nation[temp]);
        }
    }
 
    sort(final.begin(), final.end());
 
    cout<<final.size()<<"\n";
    for(int i=0; i<final.size(); i++){
        cout<<"Kingdom of "<<final[i]<<"\n";
    }
 
    return 0;
}

문제 첨부

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

16402번: 제국