[C++][BOJ] 백준 21316번: 스피카

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

21316번: 스피카

문제

위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다.

시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 잇는지 기록하였다. 하지만 어떤 별에 어떤 번호를 부여했는지 잊어버렸다고 한다.

선분들의 정보가 주어질 때, 가장 밝은 별인 Spica가 몇 번 별이였는지 알려주자.

입력

입력은 12개의 줄로 주어진다.

각 줄에는 서로 다른 두 개의 정수 x, y가 주어지며, 두 별 x와 y를 잇는 선분이 있음을 의미한다.

반드시 그림과 같은 모습임이 보장된다.

출력

입력으로 주어진 그래프에서 Spica는 몇 번 별인지 출력하여라.

번호에 해당하는 정수 하나를 출력하면 된다.

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>

int main() {

    using namespace std;
    
    vector <int> v[13]; //v[i] = i번 별에 접하는 별의 모임
    vector <int> v2[13];
    int a,b=0;
    
    //입력받고 벡터에 추가
    for(int i=0; i<12; i++){
        cin >> a >> b;
        
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=1; i<13; i++){
        
        //연결된 별이 3개인 별
        if(v[i].size() == 3){
            for(int j=0; j<3; j++) v2[i].push_back(v[v[i][j]].size());
            sort(v2[i].begin(), v2[i].end());
            if( (v2[i][0] == 1) && (v2[i][1] == 2) && (v2[i][2] == 3))
                cout << i;
        }
    }

    return 0;
}