#include "bits/stdc++.h" using namespace std; int n, minn = INT_MAX; int ppl[10]; // 각 구역 인구수 int vis[10]; vector closee[10]; // 각 구역의 인접한 구역 void dfs(int idx, int locked, int sum1){ // 1번 구역이 전부 다 차지하면 return if (locked >= n) return; // 현재 1번 선거구에서 2번 선거구 구하기 queue Q2; int vis2[10] = {}; int cnt2 = 0; int sum2 = 0; // 1번 선거구가 아닌 구역 탐색 후 push for(int i = 0; i < n; ++i){ if (vis[i] == 1) continue; vis2[i] = 1; sum2 += ppl[i]; cnt2++; Q2.push(i); break; } // 2번 선거구 구하기 while(!Q2.empty()){ int cur2 = Q2.front(); Q2.pop(); for(int dir2 = 0; dir2 < closee[cur2].size(); ++dir2){ int nx2 = closee[cur2][dir2]; if (vis2[nx2] == 1) continue; if (vis[nx2] == 1) continue; vis2[nx2] = 1; cnt2++; // 2번 선거구 갯수 + sum2 += ppl[nx2]; // 2번 선거구 인구수 + Q2.push(nx2); // 인접한 구역 push } } // 1, 2번 선거구가 구해졌으니 인구수 합 구한 후 최소값 갱신 // 1, 2번이 모든 구역을 포함해야하고, 두 선거구 모두 존재해야함 if (locked && cnt2 && locked + cnt2 == n) minn = min(minn, abs(sum1 - sum2)); // 1번 선거구 조합 모두 구하기 // 현재 구역에서 인접한 구역만 포함 for(int i = 0; i < closee[idx].size(); ++i){ int idxn = closee[idx][i]; if (vis[idxn] == 1) continue; vis[idxn] = 1; dfs(idxn, locked + 1, sum1 + ppl[idxn]); vis[idxn] = 0; } } int main() { cin >> n; for(int i = 0; i < n; ++i) cin >> ppl[i]; for(int i = 0; i < n; ++i){ int m; cin >> m; for(int j = 0; j < m; ++j){ int close_now; cin >> close_now; close_now--; closee[i].push_back(close_now); } } for(int i = 0; i < n; ++i){ vis[i] = 1; dfs(i, 1, ppl[i]); vis[i] = 0; } if (minn == INT_MAX) cout << -1 << endl; else cout << minn << endl; return 0; }

제출 #182900

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: