백준알고리즘
게리맨더링
먼지의삶
2019. 9. 20. 18:05
https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n;
int peo[11];
bool d[11];
int sum = 987654321;
bool gett =false;
vector<int> map[11];
bool vect(vector<int>&a, int x){
for(int i = 0; i<a.size(); i++){
if(x == a[i]) {
return true;
}
}
return false;
}
bool bfs(vector<int>& a){
bool x[11];
memset(x,false, sizeof(x));
if(a.size() >0) {
queue<int> q;
q.push(a[0]);
x[a[0]] = true;
while(!q.empty()){
int X = q.front(); q.pop();
for(int i = 0; i < map[X].size(); i++){
if(vect(a,map[X][i])) {
if (x[map[X][i]] == false) {
x[map[X][i]] = true;
q.push(map[X][i]);
}
}
}
}
}
for(int i = 0; i<a.size(); i++){
if(x[a[i]] == false)
return false;
}
return true;
}
void divide(vector<int>& a, vector<int>&b, int cnt ){
if(cnt == n+1){
if(a.size() == 0 ||b.size() == 0){
return;
}
else{
int ans1 = 0; int ans2 = 0;
if(bfs(a) &&bfs(b)) {
for (int i = 0; i < a.size(); i++) {
ans1 += peo[a[i]];
}
for (int i = 0; i < b.size(); i++) {
ans2 += peo[b[i]];
}
int ans = ans1 - ans2;
if (ans < 0) ans = -1 * ans;
if (sum > ans) {
/* cout << "A" << '\n';
for (int i = 0; i < a.size(); i++) {
cout << a[i] << ' ';
}
cout << '\n';
cout << 'B' << '\n';
for (int i = 0; i < b.size(); i++) {
cout << b[i] << ' ';
}
cout << '\n';
cout << ans << '\n';*/
sum = ans;
gett = true;
}
return;
}
}
}
else{
if(d[cnt] == false) {
a.push_back(cnt);
d[cnt] = true;
divide(a, b, cnt + 1);
a.pop_back();
d[cnt] = false;
b.push_back(cnt);
d[cnt] = true;
divide(a, b, cnt + 1);
b.pop_back();
d[cnt] = false;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++){
cin>>peo[i];
}
for(int i = 1; i <= n; i++){
int cos,y;
cin>>cos;
for(int j = 0; j < cos; j++){
cin>>y;
map[i].push_back(y);
}
}
vector<int> a,b;
divide(a,b,1);
if(gett)
cout<<sum<<'\n';
else
cout<<-1<<'\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
그렇게 전형적이지만은 않은 BFS문제
배열의크기자체가 굉장히작기 때문에 모든것을 다해봐도 괜찮았을문제다.
풀이방법은 다음과 같다.
1. 팀(구역) 나누기
2.나눠진 팀 검사하기
- 비어있는팀이 있을시 - > return
- BFS통해서 팀끼리 이어져있는지 확인 -> 아닐시 return
3. 합 구하고 계산하기
메커니즘 자체는 어렵지 않았다.
함정이 하나있다면, 백트랙킹처럼 검사를 하나하나 다하면서 넣는것보다는 배열이작기때문에
팀을짜고 검사를하는게 맞기도하고, 다짜고 검사하는 큰이유는
검사하면서 넣으면 문제에서 주어지는 1 3 4 , 2 4 5같이 하나씩 떨어져있는것들을 만들수없다.
참고로 역량테스트 1번문제와 유사하다.