BOJ-백준 11377번 열혈강호3 C++

✅ 문제풀이

BOJ-백준 11377번 열혈강호3 C++

dogfoot.dev 2021. 10. 23. 02:37

728x90

BOJ-백준 11377번 열혈강호3 C++ 문제 풀이 입니다.

링크 : https://www.acmicpc.net/problem/11377

11377번: 열혈강호 3

첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있

www.acmicpc.net

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std; 
// 직원 N명 할일 M개
// 일 1개 당 직원 1명
int n,m,k;
vector<int> tasksList[MAX];
int d[MAX];
bool check[MAX];

bool dfs(int x){
  for(int i=0; i<tasksList[x].size(); i++){
    int t=tasksList[x][i];
    if(check[t]) continue;
    check[t] = true;
    if(d[t]==0 || dfs(d[t])){
      d[t] = x;
      return true;
    }
  }
  return false;
}

int main() {
  scanf("%d %d %d", &n, &m, &k);
  for(int i =1; i <= n; i++) {
    int taskNum;
    scanf("%d", &taskNum);
    for(int j=0; j<taskNum; j++){
      int task;
      scanf("%d", &task);
      tasksList[i].push_back(task);
    }
  }

  int count = 0;
  for(int i=1; i<=n; i++){
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
  }

  // 직원 k명만 최대 일 2개
  // 나머지 n-k명 직원은 일 1개만 가능

  int extra =0;
  for(int p=1; p<=n && extra < k; p++){
    fill(check, check+MAX, false);
    if(dfs(p)) extra++;
  }

  cout<<count+extra<<endl;
  return 0;
}

📌 해설

이분매칭 활용 문제입니다. DFS로 해결하였습니다. 이해가 잘 안되서 다른 분들이 풀이 하신 것들을 조금 살펴봤는데 현재 코드로 작성된게 제일 직관적으로 이해하기 수월하였습니다. ㅠㅠ

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std; 
// 직원 N명 할일 M개
// 일 1개 당 직원 1명
int n,m,k;
vector<int> tasksList[MAX];
int d[MAX];
bool check[MAX];

1. 필요한 변수를 선언합니다.

1-1. n은 직원 수, m은 할일 수, k는 최대 일을 2개 할 수 있는 직원 수

1-2. tasksList는 각 직원이 할 수 있는 일의 정보들을 저장

1-3. d는 각 직원에 배정 된 일

1-4. check는 이미 배정이 처리된 일인지 확인하는 변수

bool dfs(int x){
  for(int i=0; i<tasksList[x].size(); i++){
    int t=tasksList[x][i];
    if(check[t]) continue;
    check[t] = true;
    if(d[t]==0 || dfs(d[t])){
      d[t] = x;
      return true;
    }
  }
  return false;
}

2. dfs를 수행합니다.

int main() {
  scanf("%d %d %d", &n, &m, &k);
  for(int i =1; i <= n; i++) {
    int taskNum;
    scanf("%d", &taskNum);
    for(int j=0; j<taskNum; j++){
      int task;
      scanf("%d", &task);
      tasksList[i].push_back(task);
    }
  }

  int count = 0;
  for(int i=1; i<=n; i++){
    fill(check, check+MAX, false);
    if(dfs(i)) count++;
  }

  // 직원 k명만 최대 일 2개
  // 나머지 n-k명 직원은 일 1개만 가능

  int extra =0;
  for(int p=1; p<=n && extra < k; p++){
    fill(check, check+MAX, false);
    if(dfs(p)) extra++;
  }

  cout<<count+extra<<endl;
  return 0;
}

3. main

3-1. 필요한 정보를 입력받습니다.

3-2. 1명의 직원이 1가지 일에 매칭되는 최대 횟수를 구합니다. (count)

3-3. 직원 k 명은 최대 일을 2개 할 수 있습니다.(번호가 특정되지 않았으므로 어떤 번호의 직원이든 k명은 최대 일을 2가지 배정받을 수 있습니다.) 이때 생각할 수 있는 매칭 횟수를 extra 라고 선언하고 0으로 초기화 합니다.

직원 1번부터 - N번까지 dfs를 수행하며 남은 할 일을 배정받고 매칭이 이루어지면 extra를 증가시킵니다.

단, 특정 직원 k명 까지만 dfs를 수행해야 하기 때문에 extra(추가매칭 횟수)가 k보다 클 수 없습니다.