Logo냥냠감자기술 블로그
Skip to Content
작성일: 2024-01-12

문제

백준 11375 - 열혈강호 

  • 난이도: 플레4
  • 알고리즘: 이분 매칭

코드

#include <iostream> #include <vector> using namespace std; bool dfs(int index, vector<vector<int>>& availWorks, vector<int>& matching, vector<bool>& visited) { for(int i=0; i<availWorks[index].size(); i++) { int workIndex=availWorks[index][i]; if(visited[workIndex]) { continue; } visited[workIndex]=true; if(matching[workIndex]==-1 || dfs(matching[workIndex], availWorks, matching, visited)) { matching[workIndex]=index; return true; } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int workerNum, workNum; cin>>workerNum>>workNum; vector<vector<int>> availWorks(workerNum); for(int i=0; i<workerNum; i++) { int availWorkNum; cin>>availWorkNum; availWorks[i]=vector<int>(availWorkNum); for(int j=0; j<availWorkNum; j++) { cin>>availWorks[i][j]; } } vector<int> matching(workNum+1, -1); int cnt=0; for(int i=0; i<workerNum; i++) { vector<bool> visited(workNum+1, false); if(dfs(i, availWorks, matching, visited)) { cnt++; } } cout<<cnt; }

회고

이분 매칭을 공부하면서 풀어본 문제이다. 다만 다른 이분 매칭 문제들과 풀이법이 크게 다르지도 않고, 문제를 봤을 때 이분 매칭 문제인지 알아차리는 것도 어려워 보이지 않았다. 남은 이분 매칭 문제들은 시간을 두고 조금 잊어버릴만할때 다시 한번 풀어봐야겠다