[C/C++] 백준 2188번 - 축사 배정

✏️문제 링크

https://www.acmicpc.net/problem/2188

2188번: 축사 배정

 

✏️문제 설명

 

✏️문제 풀이

기본적인 이분 매칭 구현 문제입니다.

이분 매칭 알아보기

https://pooreumjung.tistory.com/338

Algorithm 공부 #26 - 이분 매칭(Binary Matching)

 

✏️문제 코드

#include<iostream>
#include<vector>
using namespace std;
#define MAX 201
int N, M;

vector<int>graph[MAX];
int node[MAX];
bool visit[MAX];
bool dfs(int cow);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;

	for (int i = 1; i <= N; i++) { // 그래프 구현
		int number;
		cin >> number;
		while (number--) {
			int shed;
			cin >> shed;
			graph[i].push_back(shed);
		}
	}

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

	cout << count;
}

bool dfs(int cow)
{
	for (int i = 0; i < graph[cow].size(); i++) {
		int shed = graph[cow][i];
		if (visit[shed])
			continue;
		visit[shed] = true;
		if (node[shed] == 0 || dfs(node[shed])) {
			node[shed] = cow;
			return true;
		}
	}
	return false;
}

 

 

✏️다른 이분 매칭 문제 보러가기

https://pooreumjung.tistory.com/339

[C/C++] 백준 열혈강호 문제 모음 / 백준 11375번, 백준 11376번