- 어떻게 구현을 해야할까 고민이 됐었다.
- 각 구역은 A 또는 B로 반드시 구분되어야 하기 때문에 부분집합을 생각했다.
- A끼리는 모두 이어져 있어야 하고, B끼리도 모두 이어져 있어야 한다.
- bfs로 A횟수와 B횟수가 각각 1 번씩만 나와야 한다.
- 그래프는 인접행렬로 구현했다.
- 시간복잡도 : $2^{10} \times 10^2 = 102,400$ $~$
$~$ $O(2^N \times N^2)$
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
|
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final boolean A = true;
static final boolean B = false;
static int N, res;
static int[] people;
static boolean[][] edge;
static boolean[] team, visited;
static void calSum() {
Arrays.fill(visited, false);
int aCnt = 0, bCnt = 0;
int aSum = 0, bSum = 0;
for (int i = 1; i <= N; i++) {
if (team[i] == A) aSum += people[i];
else bSum += people[i];
if (visited[i]) continue;
if (team[i] == A) aCnt++;
else bCnt++;
bfs(i);
}
if (aCnt == 1 && bCnt == 1)
res = Math.min(res, Math.abs(aSum - bSum));
}
static void bfs(int start) {
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int from = q.poll();
for (int to = 1; to <= N; to++) {
if \(!edge\[from]\[to] \|| team\[from] != team\[to])
continue;
if (visited[to]) continue;
visited[to] = true;
q.offer(to);
}
}
}
static void dfs(int idx) {
if (idx >= N) {
calSum();
return;
}
team[idx] = A; dfs(idx+1);
team[idx] = B; dfs(idx+1);
}
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
res = Integer.MAX_VALUE;
N = Integer.parseInt(in.readLine());
int maxN = N + 1;
people = new int[maxN];
team = new boolean[maxN];
visited = new boolean[maxN];
edge = new boolean[maxN][maxN];
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
for (int i = 1; i <= N; i++)
people[i] = Integer.parseInt(st.nextToken());
for (int from = 1; from <= N; from++) {
st = new StringTokenizer(in.readLine(), " ");
int M = Integer.parseInt(st.nextToken());
for (int j = 0; j < M; j++) {
int to = Integer.parseInt(st.nextToken());
edge[from][to] = true;
}
}
dfs(0);
System.out.println(res == Integer.MAX_VALUE? -1 : res);
}
}
|