백준 17471번 케리맨더링 ( C++ )

문제

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

 

해설

bfs, 비트마스킹을 통해 해결

방문확인 하는 과정이 생각보다 까다로웠음

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 987654321;
int n, people[14], line[14][15], visited[14], ret = INF, total_people;
 
void bfs(int start, vector<int> v, vector<int> v2)
{
  for (int i : v)
  {
    visited[i] = 0;
  }
  for (int i : v2)
  {
    visited[i] = 1;
  }
  visited[start] = 1;
  queue<int> q;
  q.push(start);
 
  while (q.size())
  {
    int now = q.front();
    q.pop();
    for (int i = 1; i <= line[now][0]; i++)
    {
      if (visited[line[now][i]] == 0)
      {
        q.push(line[now][i]);
        visited[line[now][i]] = 1;
      }
    }
  }
}
 
void go(int num)
{
  vector<int> first, second;
  int tmp = 0;
  for (int i = 0; i < n; i++)
  {
    if (num & (1 << i))
    {
      first.push_back(i);
      tmp += people[i];
    }
    else
    {
      second.push_back(i);
    }
  }
  bfs(first[0], first, second);
  for (int i : first)
  {
    if (visited[i] == 0)
      return;
  }
  bfs(second[0], second, first);
  for (int i : second)
  {
    if (visited[i] == 0)
      return;
  }
 
  // tmp = (total_people - (2 * tmp)) > 0 ? total_people - (2 * tmp) : (2 * tmp) - total_people;
  ret = min(ret, abs(total_people - (2 * tmp)));
}
 
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> people[i];
    total_people += people[i];
  }
 
  for (int i = 0; i < n; i++)
  {
    cin >> line[i][0];
    for (int j = 1; j <= line[i][0]; j++)
    {
      int num;
      cin >> num;
      line[i][j] = num - 1;
    }
  }
 
  for (int i = 1; i < (1 << (n - 1)); i++)
  {
    go(i);
  }
 
  if (ret == INF)
  {
    cout << -1;
    return 0;
  }
  cout << ret;
}