BOJ
BOJ::17471 게리맨더링
BOJ Gold 5
BOJ::17471 게리맨더링
[BOJ] : https://www.acmicpc.net/problem/17471
- Level : Gold 5
시사점
- Bipartite 하는 문제입니다.
- 삼성 A 형 기출문제입니다.
이해(5)
- n개의 정점을 두 개의 선거구로 나눕니다.
- 나눠진 각 선거구 내에 포함된 구역들은 서로 왕래가 가능해야합니다.
설계(5)
- backtrack으로 조합을 구현하였습니다.
- 조합된 결과로 각각 선거루를 순회합니다.
- 이때 선거구 A에서 선거구 B로 갈 수 있는 조건은, 같은 색의 선거구이어야 한다는 것입니다.
- 결론적으로, 한번도 방문되지 않은 곳이 있다면, 왕래가 불가능한 곳이므로 fail입니다.
시간 복잡도
- 조합에 최대 2^10, 구역탐색에 대략 O(N)이 소모되므로, 총 O(10 * 10^3)정도의 복잡도가 예상됩니다.
공간 복잡도
구현(20)
#include<bits/stdc++.h>
const int MAX_N = 10 + 1;
const int INF = 987654321;
using namespace std;
int n, ans = INF;
int a[MAX_N];
bool visited[MAX_N];
vector<int> adj[MAX_N];
int dfs(int here, bool colur, bool team[MAX_N]){
visited[here] = true;
int sum = 0;
for(int j = 0; j < adj[here].size(); j++){
int there = adj[here][j];
if(visited[there] == false && team[there] == colur){
sum += dfs(there, colur, team);
}
}
return sum + a[here];
}
pair<int,int> dfsAll(bool team[MAX_N]){
memset(visited, false, sizeof(visited));
int sumA = 0, sumB = 0;
for(int i = 1; i <= n; i++){
if(team[i] == false){
sumA = dfs(i, false, team);
break;
}
}
for(int i = 1; i <= n; i++){
if(team[i] == true){
sumB = dfs(i, true, team);
break;
}
}
for(int i = 1; i <= n; i++)
if(visited[i] == false)
return make_pair(-1, -1);
return pair<int,int>(sumA, sumB);
}
void bipartate(int idx, bool team[MAX_N], int Asz, int Bsz){
if(idx == n+1){
if(Asz != 0 && Bsz != 0){
pair<int,int> sum = dfsAll(team);
if(sum.first != -1)
ans = min(ans, abs(sum.first - sum.second));
}
return ;
}
team[idx] = false;
bipartate(idx+1, team, Asz+1, Bsz);
team[idx] = true;
bipartate(idx+1, team, Asz, Bsz+1);
}
int main(){
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
for(int i = 1; i <= n; i++){
int cnt, tmp;
cin >> cnt;
for(int j = 0; j < cnt; j++){
cin >> tmp;
adj[i].push_back(tmp);
}
}
bool team[MAX_N]={false};
bipartate(1, team, 0, 0);
if(ans == INF) cout << "-1\n";
else cout << ans << endl;
return 0;
}
2nd try(26m)
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXV = 10 +1, inf = 0x3f3f3f3f;
using namespace std;
int V;
int a[MAXV];
bool seen[MAXV];
vector<int> adj[MAXV];
int suv[2], ans = inf;
void input(){
cin >> V;
rep(i, 1, V+1) cin >> a[i]; // 실수(5m) : MAXV까지 돌림
rep(i, 1, V+1){
int cnt; cin >> cnt;
rep(j, 0, cnt){
int x; cin >> x;
adj[i].pb(x);
}
}
}
void dfs(int here, int who, bool myTeam[MAXV]){
seen[here] = true;
suv[who] += a[here];
rep(i, 0, adj[here].size()){
int there = adj[here][i];
if(!seen[there] && myTeam[there])
dfs(there, who, myTeam);
}
}
bool able(vector<int> u, int who){
bool myTeam[MAXV] = {false};
memset(seen, false, sizeof(seen));
memset(myTeam, false, sizeof(myTeam));
rep(i, 0, u.size()) myTeam[u[i]] = true;
dfs(u[0], who, myTeam);
rep(i, 0, MAXV) if(myTeam[i] != seen[i]) return false;
return true;
}
void backtrack(int idx, vector<int> u, vector<int> v){
if(idx == V+1){
if(u.size() == 0 || v.size() == 0) return;
suv[0] = suv[1] = 0;
if(able(u, 0) && able(v, 1))
ans = min(ans, abs(suv[0] - suv[1])); // 실수(4m) : min안하고, ans계속 갱신함
return;
}
u.pb(idx); backtrack(idx+1, u, v); u.pop_back(); // 실수(1m) : idx+1해야하는데,
v.pb(idx); backtrack(idx+1, u, v); v.pop_back(); // idx보냄
}
void process(){
input();
vector<int> u, v;
backtrack(1, u, v);
if(ans == inf) cout << -1 << endl;
else cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}
디버깅(x)
2nd try
- (1m) : idx+1을 다음 재귀로 보내야 하지만, idx를 보냈습니다.
- (4m) : ans = min(ans, abs(suv[1]-suv[0])); 이지만, ans = abs(suv[1]-sub[0])로 구현하였습니다.
- (5m) : MAXV로 11을 잡아두었고, 입력으로 정점의 갯수는 V에 받았습니다.
- 하지만, 원소들을 입력받을떄 MAXV갯수만큼 입력받으려 하였습니다.