https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
먼저 그래프가 연결된 정점 정보로 주어지므로 vector 배열을 사용해서 인접 리스트를 구현해주었다.
adjlist[x] 에는 x에 연결된 정점들을 push해준다.
인구 차이가 가장 적게 나도록 선거구를 나누기 위해서는
DFS로 각 구역들을 선거구 1에 넣는 경우와 선거구 2에 넣는 경우를 모두 구해서 계산해본다.
선거구에 넣을 때, 나중에 BFS탐색 시 연결되어 있는지 확인하기 위해서 check배열을 추가적으로 사용하였다.
선거구 1에 넣는 경우는 check배열의 값을 true로 선거구 2에 넣는 경우는 check배열의 값을 false로 하였다.
각각의 경우에서 BFS탐색으로 한 선거구에 포함되어 있는 구역이 모두 연결되어 있는지 검사해줘야 하는데, 선거구 1과 선거구 2를 각각 BFS로 검사해줬다.
먼저 선거구 1을 검사할 때는 선거구에 있는 지역 하나를 처음에 큐에 넣고 연결된 구역들을 방문하며 방문 체크를 한다.
이때, check배열의 값이 false인 경우(선거구 2인 경우) 방문하지 못한다. BFS탐색이 끝난 후에 같은 선거구인데 방문하지 않았다면 한 선거구 내에 연결되지 않은 구역이 있다는 뜻이므로 false를 리턴한다.
마찬가지로 선거구 2를 검사할 때에도 check배열의 값이 true인 경우 (선거구 1인 경우)를 방문하지 않고 연결된 정점들을 모두 방문한다. 그리고 선거구 내에 방문하지 않은 구역이 있다면 false를 리턴한다.
위의 두 가지 경우에서 모두 false를 리턴하지 않았다면 두 선거구가 모두 각 선거구 내의 구역들이 연결되어 있다는 뜻이므로 true를 리턴하고 인구 차이를 계산한다.
/*구역의 수가 최대 10개이고, 각 구역의 인구수가 최대 100명이므로 두 구역의 인구 차이가 최대 1000명을 넘지 않으므로 정답을 저장할 ans변수의 초기값을 1000으로 해두었다 */
|
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
int ans;
//인구 수 저장
int arr[11];
//인접리스트
vector<int> adjlist[11];
//선거구 1
vector<int> vt1;
//선거구 2
vector<int> vt2;
//선거구 1인 경우 true, 선거구 2인 경우 false
bool check[11];
//BFS할때 방문체크 배열
bool visit[11];
bool bfs() {
//방문배열 초기화
for (int i = 0; i <= n; i++) visit[i] = false;
//선거구 1이 모두 연결되어 있는지 검사
queue<int> q;
q.push(vt1[0]);
visit[vt1[0]] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
//현재 구역과 연결된 구역들을 검사한다
int size = adjlist[x].size();
for (int k = 0; k < size; k++) {
int nx = adjlist[x][k];
//이미 방문한 경우
if (visit[nx]) continue;
//선거구 2인 경우
if (!check[nx]) continue;
visit[nx] = true;
q.push(nx);
}
}
//선거구 1에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
for (int x : vt1) {
if (!visit[x]) return false;
}
//방문배열 초기화
for (int i = 0; i <= n; i++) visit[i] = false;
//선거구 2가 연결되어 있는지 검사
q.push(vt2[0]);
visit[vt2[0]] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
int size = adjlist[x].size();
for (int k = 0; k < size; k++) {
int nx = adjlist[x][k];
if (visit[nx]) continue;
//선거구 1인경우
if (check[nx]) continue;
visit[nx] = true;
q.push(nx);
}
}
//선거구 2에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
for (int x : vt2) {
if (!visit[x]) return false;
}
//각 선거구가 모두 연결되어 있다면 true를 리턴
return true;
}
void calc() {
if (bfs()) {//각 선거구가 모두 연결되어 있다면 인구차이를 계산
int sum = 0;
//선거구 1과 선거구 2의 인구차이를 구한다.
for (int x : vt1) sum += arr[x];
for (int x : vt2) sum -= arr[x];
if (sum < 0) sum = -sum;
//최솟값보다 적다면 최솟값 갱신
if (ans > sum) ans = sum;
}
}
void solve(int index) {
if (index > n) {
//선거구에는 최소 1개의 구역이 포함되어야 한다
if (vt1.size() == 0 || vt2.size() == 0) return;
//인구차이를 계산
calc();
return;
}
//index구역을 선거구 1에 넣는 경우
vt1.push_back(index);
check[index] = true;
solve(index + 1);
check[index] = false;
vt1.pop_back();
//index구역을 선거구 1에 넣는 경우
vt2.push_back(index);
solve(index + 1);
vt2.pop_back();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
int cnt, x;
for (int i = 1; i <= n; i++) {
cin >> cnt;
for (int j = 0; j < cnt; j++) {
cin >> x;
adjlist[i].push_back(x);
}
}
ans = 1000;
solve(1);
//ans값이 갱신되지 않았다면 두 선거구로 나눌수없는 경우이다.
if(ans != 1000) cout << ans << '\n';
else cout << -1 << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17472. 다리 만들기 2 (0) | 2019.10.16 |
|---|---|
| [BOJ] 2146. 다리 만들기 (0) | 2019.10.16 |
| [BOJ] 17141. 연구소 2 (0) | 2019.09.06 |
| [BOJ] 6359. 만취한 상범 (0) | 2019.09.04 |
| [BOJ] 1931. 회의실배정 (0) | 2019.09.02 |