[C/C++] 백준 17471 - 게리맨더링

[C/C++] 백준 17471 - 게리맨더링

https://www.acmicpc.net/problem/17471

골드 4치고는 체감상 굉장히 어려웠다. 구현 실수하기도 좋고 접근 방법이 잘못된 경우가 많아서 주의가 필요하다.

우선 문제를 보면 기본적으로 그래프를 사용하는 문제 + 각각의 경우의 수를 봐야하므로 브루트포스가 섞인 것을 확인할 수 있다.

이 문제에서 주의할 점은 2가지 선거구 모두 각각의 노드들끼리 연결된 상태여야 한다는 것으로 내가 고른 구역과 내가 고르지 않은 구역 모두 탐색을 돌려서 각각의 노드들끼리 연결되어있는지 확인해봐야한다.

내가 구현한 방법은 모든 경우의 수를 대상으로 각각의 케이스마다 내가 고른 노드 bfs, 내가 고르지 않은 노드 bfs 탐색을 돌려서 연결되어있는지 확인하고 불가능한 방법이 아니라면 값을 계산해서 최소인지 비교하는 방식으로 진행했다.

탐색에서도 중간에 오류가 생겼었는데 내가 선택하지 않은 구역에 대해서 방문한걸로 처리하지 않아 원래는 도달 불가능한 노드도 도달하는 오류가 발생했다. -> 이런 일이 생기지 않도록 항상 결과를 제대로 확인하고 제출하자

#include #include #include #include #include #include using namespace std; #define INF 210000000 int arr[11][11]; int num[11]; int n,m, ans = INF; bool selected[11]; vector node[2]; queue q; int bfs(int flag) { int x, nx; int ret = 0, cnt = 0; bool visit[2][11]; bool check[11] = {}; for (int i = 0; i < 2; i++) { for (int j = 0; j <= 10; j++) check[j] = visit[i][j] = false; } int idx; // 선택하지 않은 구역은 이미 방문된걸로 처리해야 탐색에 오류가 안생김 // 안그러면 도달하지 못하는 곳도 가게됨 for (int i = 0; i < node[!flag].size(); i++) { idx = node[!flag][i]; visit[flag][idx] = true; } for (int i = 0; i < node[flag].size(); i++) check[node[flag][i]] = true; q.push(node[flag][0]); while (!q.empty()) { x = q.front(); visit[flag][x] = true; if (check[x]) { check[x] = false; ret += num[x]; cnt++; } for (int i = 1; i <= n; i++) { if (arr[x][i] && visit[flag][i] == false) q.push(i); } q.pop(); } if (cnt != node[flag].size()) return -1; return ret; } void selectNode(int idx) { int r1 = 0, r2 = 0; if (idx == n) { for (int i = 1; i <= n; i++) node[selected[i]].push_back(i); // 하나도 없는 경우는 제외 if (node[0].size() == 0 || node[1].size() == 0) { node[0].clear(); node[1].clear(); return; } r1 = bfs(0); r2 = bfs(1); if(r1 != -1 && r2 != -1) { ans = min(ans, abs(r1 - r2)); } node[0].clear(); node[1].clear(); return; } selected[idx] = true; selectNode(idx + 1); selected[idx] = false; selectNode(idx + 1); return; } int main(void) { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin >> n; int k; for (int i = 1; i <= n; i++) cin >> num[i]; for (int i = 1; i <= n; i++) { cin >> m; for (int j = 0; j < m; j++) { cin >> k; arr[i][k] = arr[k][i] = 1; } } selectNode(1); if (ans != INF) cout << ans << endl; else cout << "-1

"; return 0; }

from http://lts96.tistory.com/15 by ccl(A) rewrite - 2021-10-31 18:01:08