[백준] 11578 팀원 모집

November 02, 2021 ( last updated : November 02, 2021 )
비트마스킹 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 11578번 팀원 모집

[백준] 11578번 팀원 모집

백준 11578번

알고리즘 유형

풀이방법

팀원 모집시 모든 경우의 수를 순회하는데 dfs로 순회하고 기저 조건은 현재 멤버로 모든 문제를 풀었을 경우이다.

멤버들이 모든 문제를 풀 수 있는지 확인은 속도를 위해 비트마스킹으로 한다.

#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<31) - 1
int N, M, Q = 0;
int SOL[11] = {
    0,
};
int MIN = 11;
vector<int> member;

bool is_solved() {
  int solve = 1;
  for (int i=0; i<member.size(); i++) {
    solve |= (SOL[member[i]] & Q);
  }

  if(solve == Q) {
    return true;
  } else {
    return false;
  }
}

void find( int index) {
  if (is_solved()) {
    if(MIN > member.size()) {
      MIN = member.size();
    }
    return;
  }
  for (int i=index; i<M; i++) {
    member.push_back(i);
    find(i+1);
    member.pop_back();
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  
  cin.tie(0);
  cout.tie(0);
  cin >> N >> M;

  Q = (1 << (N+1)) - 1;
  for (int i=0; i<M; i++) {
    int cnt;
    cin >> cnt;

    for (int j=0; j<cnt; j++) {
      int tmp;
      cin >> tmp;
      SOL[i] |= 1 << tmp;
    }
  }

  find(0);

  if(11 == MIN) {
    cout << -1;
  } else {
    cout << MIN;
  }
  return 0;
}

Originally published November 02, 2021
Latest update November 02, 2021

Related posts :

{# #}