브루트 포스/브루트포스(재귀)

게리맨더링

4gats 2023. 9. 18. 20:23

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
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
160
161
162
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
 
using namespace std;
 
int ans = 1004;
int n;
int population[15];
bool region[15];
vector<vector<int>> graph;
bool visited[15];
 
 
bool check()
{
    memset(visited, false, sizeof(visited));
 
    int a_cnt = 0;
    int b_cnt = 0;
 
    queue<int> a_q;
    queue<int> b_q;
 
    for (int i = 1; i <= n; i++)
    {
        if (region[i])
        {
            a_cnt++;
            visited[i] = true;
            a_q.push(i);
            break;
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (!region[i])
        {
            b_cnt++;
            visited[i] = true;
            b_q.push(i);
            break;
        }
    }
 
    if (a_cnt == 0 || b_cnt == 0)
        return false;
    
 
    while (!a_q.empty())
    {
        int now = a_q.front();
        a_q.pop();
 
        for (int next : graph[now])
        {
            if (visited[next] == false && region[next] == true)
            {
                visited[next] = true;
                a_cnt++;
                a_q.push(next);
            }
        }
    }
 
    while (!b_q.empty())
    {
        int now = b_q.front();
        b_q.pop();
 
        for (int next : graph[now])
        {
            if (visited[next] == false && region[next] == false)
            {
                visited[next] = true;
                b_cnt++;
                b_q.push(next);
            }
        }
    }
 
    if (a_cnt + b_cnt == n)
        return true;
    else
        return false;
}
 
void calculate()
{
    int a_hap = 0;
    int b_hap = 0;
    for (int i = 1; i <= n; i++)
    {
        if (region[i])
            a_hap += population[i];
        else
            b_hap += population[i];
    }
 
    if (ans > abs(a_hap - b_hap))
        ans = abs(a_hap - b_hap);
}
 
 
void go(int index, int cnt)
{
    if (cnt >= 1)
    {
        if (check())
        {
            calculate();
        }
    }
 
    for (int i = index; i <= n; i++)
    {
        if (region[i])
            continue;
        region[i] = true;
        go(i, cnt + 1);
        region[i] = false;
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> population[i];
    }
 
    graph.resize(n + 5);
    for (int i = 1; i <= n; i++)
    {
        int gaesu;
        cin >> gaesu;
        for (int j = 0; j < gaesu; j++)
        {
            int a;
            cin >> a;
            graph[i].push_back(a);
        }
    }
    
    go(1, 0);
    if (ans == 1004)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
    
    return 0;
}
 cs

a 지역, b 지역 2개로 나뉜다?

선택 / not 선택

n과 m, 치킨 배달 문제에서 했다.

이 문제의 다른 점은

정해진 개수가 없다는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void go(int index, int cnt)
{
    if (cnt >= 1)
    {
        if (check())
        {
            calculate();
        }
    }
 
    for (int i = index; i <= n; i++)
    {
        if (region[i])
            continue;
        region[i] = true;
        go(i, cnt + 1);
        region[i] = false;
    }
}
 cs

이렇게 하면 되고!

 

개수를 세는 것은 visited를 true로 바꿀 때 ++ 해주면 된다.

ans가 바뀌지 않았다면 -1 출력.