반응형
https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
[ 문제풀이 ]
1. 조합을 이용하여 두 구역으로 나눕니다.
2. 각 구역에 있는 노드들끼리 연결되어 있는지 체크 후 연결되어 있다면 true를 반환하고 그렇지 않다면 false를 반환합니다.
3. true를 반환했다면 두 구역의 인구수 차를 ans와 비교하여 더 낮은 값을 ans에 저장합니다.
4. ans의 값이 초깃값이면 -1을 출력하고 그렇지 않다면 ans를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<vector> #include<queue> using namespace std; int N; int pop[11]; vector<int> list[11]; int population; int box[11]; int cur; int ans = 987654321; bool bfs() //두 구역으로 나누어지는 지 체크 { int visited[11] = { 0 }; queue<int> q; for (int i = 1; i <= N; i++) { if (box[i] == 1) { q.push(i); break; } } while (!q.empty()) { //첫번째 구역 int cur = q.front(); q.pop(); if (box[cur] == 0) continue; if (visited[cur] == 1) continue; visited[cur] = 1; for (auto next : list[cur]) { if (visited[next] != 1) { q.push(next); } } } for (int i = 1; i <= N; i++) { if (visited[i] != box[i]) return false; } for (int i = 1; i <= N; i++) { if (visited[i] != 1) { q.push(i); break; } } while (!q.empty()) { //두번째 구역 int cur = q.front(); q.pop(); if (visited[cur] == 1) continue; visited[cur] = 1; for (auto next : list[cur]) { if (visited[next] != 1) { q.push(next); } } } for (int i = 1; i <= N; i++) { if (visited[i] == 0) return false; } return true; } void dfs(int level, int limit, int n) { if (level == limit) { int temp = population - cur; int diff = abs(temp - cur); //두 구역의 인구 차이 if (bfs()) { //두 구역으로 나누어 졌다면 ans = min(diff, ans); } return; } for (int i = n; i <= N; i++) { //조합 뽑기 box[i] = 1; cur += pop[i]; dfs(level + 1, limit, i + 1); box[i] = 0; cur -= pop[i]; } } int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &pop[i]); population += pop[i]; } for (int i = 1; i <= N; i++) { int num; scanf("%d", &num); for (int j = 0; j < num; j++) { int to; scanf("%d", &to); list[i].push_back(to); } } for (int i = 1; i <= N / 2; i++) { dfs(0,i,1); } if (ans == 987654321) { printf("%d", -1); return 0; } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 21608번 - 상어 초등학교 (C++) (0) | 2022.09.06 |
---|---|
[ 백준 ] 11403번 - 경로 찾기 (C++) (0) | 2022.09.05 |
[ 백준 ] 1003번 - 피보나치 함수 (C++) (0) | 2022.09.03 |
[ 백준 ] 16234번 - 인구 이동 (C++) (0) | 2022.09.02 |
[ 백준 ] 17135번 - 캐슬 디펜스 (C++) (0) | 2022.09.01 |