반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 6987
- 처우협의
- boj #19237 #어른 상어
- msSQL
- 기술면접
- dfs
- Docker
- 백준
- OFFSET
- 연결요소
- 물채우기
- 이분탐색
- upper_bound
- 경력
- 처우산정
- 파라메트릭
- 매개변수탐색
- 백트래킹
- softeer
- BOJ
- BFS
- incr
- compose
- 13908
- 성적평가
- Kafka
- 오퍼레터
- @P0
- 퇴사통보
- 소프티어
Archives
- Today
- Total
기술 블로그
17471번 게리맨더링 본문
728x90
반응형
https://www.acmicpc.net/problem/17471
공부겸 오랜만에 풀어본 문제다.
#include <bits/stdc++.h>
using namespace std;
/*
1. 두 선거구로 나누기 - 백트래킹
2. 각 선거구 내 구역들이 인접한지 check - bfs
3. 모두 인접해있다면, 두 선거구의 총인구합 구하기 - 구현
*/
int N, person[11]; // person[i] : i번째 구역 인구 수
int ans = 2e9;
vector<int> v[11];
bool used[11], num[11];
bool chk(vector<int> a, vector<int> b) {
memset(used, false, sizeof(used));
queue<int> q;
used[a[0]] = true;
q.push(a[0]);
// a선거구 내에서만 움직여야 하므로, 미리 b선거구를 방문 처리 표시한다.
// 그래서 a선거구에서 b선구로갔다가 다시 a선거구로 가는 경우를 막는다.
for (auto i : b) {
used[i] = true;
}
while (!q.empty())
{
int qs = q.size();
while (qs--)
{
int now = q.front();
q.pop();
for (auto next : v[now]) {
if (!used[next]) {
used[next] = true;
q.push(next);
}
}
}
}
for (auto i : a) {
if (!used[i]) {
return false;
}
}
return true;
}
void bt(vector<int> & a, int st) {
if (!a.empty() && a.size() != N) {
vector<int> b;
for (int i = 1; i <= N; i++) {
if (!num[i]) {
b.push_back(i);
}
}
/*printf("■■■■■■■■■■■■■\n");
for (auto i : a) printf("%d ", i);
printf("\n");
for (auto i : b) printf("%d ", i);
printf("\n");
printf("■■■■■■■■■■■■■\n");*/
if (chk(a, b) && chk(b, a)) {
int sa = 0, sb = 0;
for (auto i : a) sa += person[i];
for (auto i : b) sb += person[i];
ans = min(ans, abs(sa - sb));
}
}
for (int i = st; i <= N; i++) {
a.push_back(i);
num[i] = true;
bt(a, i + 1);
num[i] = false;
a.pop_back();
}
}
int main()
{
cin.tie(0);
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &person[i]);
}
for (int i = 1; i <= N; i++) {
int cnt = 0;
scanf("%d", &cnt);
for (int j = 0; j < cnt; j++) {
int vilg = 0;
scanf("%d", &vilg);
v[i].push_back(vilg);
}
}
vector<int> a;
bt(a, 1);
printf("%d\n", ans == 2e9 ? -1 : ans);
return 0;
}
728x90
반응형
'알고리즘 문제 > BOJ' 카테고리의 다른 글
18430번 무기 공학 (0) | 2022.05.04 |
---|---|
2138번 전구와 스위치 (0) | 2022.05.03 |
9935번 문자열 폭발 (0) | 2022.04.24 |
15683번 감시 (0) | 2022.03.09 |
2660번 회장뽑기 (0) | 2022.02.06 |