BOJ-백준 11375번 열혈강호 C++

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

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

11375번: 열혈강호

 

 

 

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

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std; 
// 직원 N명 할일 M개
// 일 1개 당 직원 1명
int n,m;
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", &n, &m);
  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++;
  }
  cout<<count;
}

 

📌 해설

DFS를 이용한 이분탐색 문제입니다. 직원 1명당 1개의 일을 할 수 있고 각 직원의 할일이 입력으로 주어졌을때 겹치지 않고 1대 1 매칭 될 수 있는 최대 매칭 수를 구하는 문제입니다. 

 

 

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

1. 이분매칭에 필요한 변수를 모두 선언해줍니다. 

1-1. n,m은 직원 수와 할일의 갯수입니다. 

1-2. tasksList에는 각 직원이 할 수있는 일의 정보를 저장합니다. 

1-3. d 에는 매칭 결과를 저장합니다.

1-4. check에는 각 할일의 매칭이 이미 처리된 할일이면 true 아직 처리하지 않은 할일이면 false를 담습니다. 

 

 

int main() {
  scanf("%d %d", &n, &m);
  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++;
  }
  cout<<count;
}

2. main에서는 필요한 정보를 입력받고 dfs를 수행합니다. 각 dfs가 끝났을때 매칭이 이루어 졌으면 count합니다. 

모든 dfs가 수행되면 count를 반환합니다. 

 

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;
}

3. dfs를 수행합니다. 직원 번호를 매개변수로 받습니다. 

3-1. 직원이 할 수 있는 일(매칭 가능한 할일 번호)를 탐색하는 for문을 작성합니다. 

3-2. 할수 있는 일의 번호를 t에 저장합니다. 

3-3. 만약 이미 매칭이 처리된 할 일이면 pass합니다. 

3-4. 할일 번호 t 를 처리 하였다고 표시하고, 할일 t에 배정된 직원이 아무도 없다면 직원 x에 t를 배정합니다. (d[t] = x)

3-5. 이미 t에 배정된 직원이 있다면 그 직원을 다시 dfs 수행하여 다른 할일과 매칭되었다면( true 반환) 할일 t에 x를 배정하고 dfs를 종료합니다. 

3-6. 매칭이 실패하면 false를 반환합니다. 

 

 

 

 

::