boj 21316 스피카

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

 

12개 간선이 입력으로 주어지고, 어떤 입력이든 이 모양으로 주어진다고 합니다.

여기서 Spica가 되는 정점의 조건은 주변 정점들과 간선들로 알아낼 수 있습니다.

 

저는 Spica에 인접한 정점들은 각각 1, 2, 3개의 간선이 있다는 것을 파악했고, 그대로 구현했습니다.

1, 2, 3개는 각각 비트마스킹을 활용했습니다.

 

 

#include <iostream>
#include <vector>
#define MAX 13
using namespace std;
 
vector<int> v[MAX];
 
void func() {
    for (int i = 1; i < MAX; i++) {
        int flag = 0;
        for (auto next : v[i]) {
            flag |= (1 << (v[next].size() - 1));
        }
 
        if (flag == 7) {
            cout << i << '\n';
            return;
        }
    }
}
 
void input() {
    int x, y;
    for (int i = 1; i < MAX; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}