17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
선거구를 두 구간으로 나누는데 나눠진 구간끼리 연결되어 있어야합니다.
dfs기반의 부분집합으로 나눌 수 있는 모든 구간을 확인합니다.
두 구간을 div1, div2라는 리스트를 사용하였고, 구역들끼리 연결되어있는지 bfs를 통해 확인합니다.
구간의 모든 구역끼리 연결되어 있으면 구역들의 합의 최솟값을 갱신합니다.
두 선거구로 나눌 수 없는 경우가 입력으로 주어질 수 있으니 그 때는 -1을 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer> graph[] = new ArrayList[11];
static ArrayList<Integer> div1 = new ArrayList<>();
static ArrayList<Integer> div2 = new ArrayList<>();
static int list[] = new int[11];
static boolean pick[] = new boolean[11];
static boolean visit[] = new boolean[11];
static int N, ans = 2147483647;
static boolean bfs(ArrayList<Integer> div, int size, boolean t) {
Arrays.fill(visit, false);
Deque<Integer> dq = new ArrayDeque<>();
dq.add(div.get(0));
visit[div.get(0)] = true;
int cnt = 0;
while (!dq.isEmpty()) {
int x = dq.poll();
cnt++;
for (int i = 0; i < graph[x].size(); i++) {
int next = graph[x].get(i);
if (visit[next] || pick[next] != t)
continue;
visit[next] = true;
dq.add(next);
}
}
if (cnt == size)
return true;
else
return false;
}
static void func(int idx) {
if (!div1.isEmpty()) {
for (int i = 1; i <= N; i++) {
if (!pick[i])
div2.add(i);
}
if(!div2.isEmpty()) {
if (bfs(div1, div1.size(), true)) {
if (bfs(div2, div2.size(), false)) {
int sum = 0;
for (int i = 0; i < div1.size(); i++) {
sum += list[div1.get(i)];
}
for (int i = 0; i < div2.size(); i++) {
sum -= list[div2.get(i)];
}
ans = Math.min(ans, Math.abs(sum));
}
}
div2.clear();
}
}
for (int i = idx; i <= N; i++) {
div1.add(i);
pick[i] = true;
func(i + 1);
pick[i] = false;
div1.remove(div1.size() - 1);
}
}
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
int K, v;
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
graph[i] = new ArrayList<>();
while (K-- > 0) {
v = Integer.parseInt(st.nextToken());
graph[i].add(v);
}
}
}
static void print() {
if (ans == 2147483647)
System.out.println(-1);
else
System.out.println(ans);
}
public static void main(String[] args) throws Exception {
input();
func(1);
print();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 17244 아맞다우산 (0) | 2021.11.25 |
|---|---|
| boj 1194 달이 차오른다, 가자. (0) | 2021.04.21 |
| boj 2573 빙산 (0) | 2021.04.05 |
| boj 14923 미로 탈출 (0) | 2021.03.29 |
| boj 17836 공주님을 구해라! (0) | 2021.03.26 |