https://www.acmicpc.net/problem/21316
12개 간선이 입력으로 주어지고, 어떤 입력이든 이 모양으로 주어진다고 합니다.
여기서 Spica가 되는 정점의 조건은 주변 정점들과 간선들로 알아낼 수 있습니다.
저는 Spica에 인접한 정점들은 각각 1, 2, 3개의 간선이 있다는 것을 파악했고, 그대로 구현했습니다.
1, 2, 3개는 각각 비트마스킹을 활용했습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#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;
}
|
cs |
'algorithm > ad-hoc' 카테고리의 다른 글
| boj 24553 팰린드롬 게임 (0) | 2024.08.07 |
|---|---|
| boj 14370 전화번호 수수께끼 (Large) (0) | 2024.08.06 |
| boj 10350 Banks (0) | 2024.07.31 |
| boj 5527 전구 장식 (0) | 2024.07.30 |
| boj 14864 줄서기 (0) | 2024.07.26 |