[BOJ] 11375 : 열혈강호

Drakk·2021년 8월 12일
0

알고리즘 문제풀이

목록 보기
21/22
post-thumbnail

💉문제 내용

문제 풀러가기

💉입출력

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

🧺출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

🔋예제 입출력

🔮예제 입력1

5 5
2 1 2
1 1
2 2 3
3 3 4 5
1 1

🔮예제 출력1

4

💉문제 분석

🔋분류

DFS, 이분매칭, 최대유량, 네트워크 유량

🔋난이도

플래티넘IV

💉문제 풀이

🔋해법

그냥 이분매칭 구현문제였습니다.
이때 주의할것이있는데 M은 사용이안되더라구요.
M개의 일중에 최대라고해서 M번 돌려주는건줄 알았더니, 아니네요;;(뭐지..?)

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 1001;
constexpr int INF = 1e9+7;

std::vector<int> adj[MAX];

int d[MAX];
bool visit[MAX];

bool dfs(int current){
	for(int i=0;i<adj[current].size();++i){
		int next = adj[current][i];
		
		if(visit[next]) continue;
		visit[next] = true;
		
		if(d[next] == 0 || dfs(d[next])){
			d[next] = current;
			return true;
		}
	}
	
	return false;
}

int BipartiteMatching(int N){
	int count = 0;
	
	for(int i=1;i<=N;++i){
		memset(visit, false, sizeof(visit));
		if(dfs(i)) ++count;
	}
	
	return count;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int N, M;
	
	std::cin >> N >> M;
	
	for(int i=1;i<=N;++i){
		int T;
		std::cin >> T;
		
		for(int j=0;j<T;++j){
			int a;
			std::cin >> a;
			
			adj[i].push_back(a);
		}
	}
	
	std::cout << BipartiteMatching(N);
}




N이랑 M헷갈려서 한번 틀렸네용.
4일만에 푸는 알고리즘문제네용ㅋㅋ
요즘에 웹앱개발에 빠져가지고, 알고리즘문제를 통안풀었습니다.

손풀기겸 이분매칭문제 하나풀었습니다.
앱은 코틀린배우고있고, 웹쪽은 html, css, js(jquery)등등 배우는중입니다.

나중에 웹개발감각좀 생기면 php도 도전해봐야겠군요..!

게임, 웹, 그림 모두 마스터하는 그날까지!

(그림은 워낙 똥손이라서, 이번생애 애니일러 그려보는게 꿈인데 가능할까요..ㅠㅠ)

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~~

profile
C++ / Assembly / Python 언어를 다루고 있습니다!

0개의 댓글