Korcp
diff --git a/‎0x0D/solutions/17471.cpp
Lines changed: 105 additions & 5 deletions b/‎0x0D/solutions/17471.cpp
Lines changed: 105 additions & 5 deletions
@@ -1,11 +1,111 @@
-// Authored by : BaaaaaaaaaaarkingDog
+// Authored by : scsc3204
 // Co-authored by : -
-// http://boj.kr/****************
+// http://boj.kr/85b770d684b942b6994994606010adc0
 #include <bits/stdc++.h>
 using namespace std;
 
-int main(void){
+const int INF = 0x7f7f7f7f;
+const int MX = 10;
+
+int n, ans = INF;
+int viscnt;
+
+int po[MX + 2];
+bool vis[MX + 2];
+
+vector<bool> comb;
+vector<int> adj[MX + 2];
+
+queue<int> q;
+
+void bfs(int st) {
+  bool code = comb[st];
+  vis[st] = 1;
+  viscnt++;
+  q.push(st);
+
+  while(!q.empty()) {
+    int cur = q.front(); q.pop();
+    for(int nxt : adj[cur]) {
+      if(vis[nxt] || comb[nxt] != code) continue;
+      vis[nxt] = 1;
+      viscnt++;
+      q.push(nxt);
+    }
+  }
+}
+
+void solve(int m) {
+  fill(comb.begin(), comb.end(), 0);
+
+  for(int i = n - m; i < n; i++)
+    comb[i] = 1;
+  
+  do {
+    viscnt = 0;
+    fill(vis, vis + n, 0);
+
+    for(int i = 0; i < n; i++)
+      if(!comb[i]) { bfs(i); break; }
+    for(int i = 0; i < n; i++)
+      if(comb[i]) { bfs(i); break; }
+
+    if(viscnt != n) continue;
+
+    int tmp = 0;
+    for(int i = 0; i < n; i++) {
+      if(comb[i]) tmp += po[i];
+      else tmp -= po[i];
+    }
+    tmp = abs(tmp);
+    ans = min(tmp, ans);
+  } while(next_permutation(comb.begin(), comb.end()));
+}
+
+int main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
-  
-}
+
+  cin >> n;
+  for(int i = 0; i < n; i++)
+    cin >> po[i];
+  for(int i = 0; i < n; i++) {
+    int m; cin >> m;
+    while(m--) {
+      int x; cin >> x;
+      adj[i].push_back(x - 1);
+    }
+  }
+
+  comb.resize(n);
+  for(int i = 1; i <= n / 2; i++)
+    solve(i);
+  if(ans == INF) ans = -1;
+  cout << ans;
+}
+/*
+next_permutation을 활용해 comb가 1인 구역을 하나씩 늘린다.
+이로써 n개 구역 중 1개 구역부터 n/2개 구역까지 선택하며 선거구를 구성한다.
+구역이 속한 선거구는 comb 값에 따라 구분한다.
+
+이같이 구현하는 경우, 0011과 1100을 다른 경우로 판단해 중복 연산이 발생한다.
+그러나, n이 가장 클 때인 10개 구역에 대해서
+1명부터 5명씩 팀을 나누는 경우가 10C1 + 10C2 + 10C3 + 10C4 + 10C5이고
+이들은 10 + 45 + 120 + 210 + 252 = 637이기 때문에,
+더 효율적으로 팀을 나눌 필요는 없다고 판단하였다.
+
+문제를 그래프로 구현했다.
+문제의 구역 번호는 1-indexed지만, 편의상 0-indexed로 바꿔 구현하였다(69-75번째 줄).
+
+구역 중 comb 값이 0인 경우와 1인 경우를 하나씩 찾아 bfs를 수행(45-48번째 줄)한다.
+이때, 인접한 구역 중 동일 선거구에 속한 구역만 방문하고 큐에 넣는다(26-31번째 줄).
+
+만약 comb 값이 0인 구역과 1인 구역에 대한 bfs를 마친 뒤에도 
+방문횟수를 세는 viscnt 변수가 n에 도달하지 못했다면,
+이는 인접하지 않은 구역이 있는 것이므로
+인구 차이를 계산하지 않고 다음 경우로 넘어간다.
+
+이같이 계산된 최솟값을 답으로 출력한다.
+만약, 모든 경우에 대해 선거구가 나눠지지 않는다면
+ans은 갱신되지 않아 INF이므로, 이 경우 -1을 출력한다.
+*/