백준 2186 축사 배정 C++ 기록

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

2188번: 축사 배정

 이 문제는 최대한 많은 수의 소가 축사에 배정될 때의 소의 수를 구하는 문제이다. 이는 전형적인 이분 매칭 문제이다. 이분 매칭은 이 곳(https://blog.naver.com/ndb796/221240613074)을 참고하였다.

1.  소와 축사 수를 입력 받는다. 그리고 각 소별로 원하는 축사들을 입력받고 저장한다.
2. 각 소별로 축사를 배정할 수 있는지 검사한다. 
3. 현재 소가 원하는 축사들을 전부 검사한다. 
   1. 만약 이미 배정된 축사라면, 그 축사는 검사를 패스한다.
   2.  만약 아직 배정된 소가 없거나, 그 소를 다른 축사로 옮길 수 있다면 이 축사에 현재 소를 배정허고 true를 반환한다.
   3. 끝까지 배정되지 않은 경우 false를 반환한다.
4. 만약 배정에 성공하였다면 answer의 값을 1 증가시킨다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#pragma warning(disable:4996)

using namespace std;

#define MAX 201

int answer = 0;	// 가장 많이 배정된 소의 수
int cowNum, cattleShedNum;	// 각각 총 소의 수, 축사 수
bool isMatched[MAX];		// 축사가 배정되었다면 true, 아니면 false
int whichCow[MAX];			// 각 축사별 소
vector<int> hopes[MAX];		// 각 소들이 원하는 축사들

bool Match(int cow)
{	
	// 3. 현재 소가 원하는 축사들을 전부 검사한다. 
	for (int i = 0; i < hopes[cow].size(); ++i)
	{
		int cattleShed = hopes[cow][i];	// 소가 원하는 축사
		
        // 3-1. 만약 이미 배정된 축사라면 패스한다.
		if (isMatched[cattleShed] == true)
			continue;
		isMatched[cattleShed] = true;
	
    	// 3-2. 만약 아직 배정된 소가 없거나, 그 소를 다른 축사로 옮길 수 있다면 
        // 이 축사에 현재 소를 배정허고 true를 반환한다.
		if (whichCow[cattleShed] == 0 || Match(whichCow[cattleShed]))
		{
			whichCow[cattleShed] = cow;
			return true;
		}
	}
	
    // 3-3. 끝까지 배정되지 않은 경우 false를 반환한다. 
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);	
	
    // 1. 소와 축사 수를 입력 받는다. 
    // 그리고 각 소별로 원하는 축사들을 입력받고 저장한다.
	cin >> cowNum >> cattleShedNum;	

	for (int cow = 1; cow <= cowNum; ++cow)
	{	
		int hopeNum;	// 소별로 원하는 축사의 수
		cin >> hopeNum;

		for (int h = 0; h < hopeNum; ++h)
		{
			int cattleShed;		// 소가 원하는 축사 번호
			cin >> cattleShed;

			hopes[cow].push_back(cattleShed);	// 저장
		}
	}
	
    // 2. 각 소별로 축사를 배정할 수 있는지 검사한다. 
	for (int cow = 1; cow <= cowNum; ++cow)
	{
		memset(isMatched, false, sizeof(isMatched));
	
    	// 4. 만약 배정에 성공하였다면 answer의 값을 1 증가시킨다.
		if (Match(cow)==true)
			++answer;
	}

	cout << answer << endl;

	return 0;
}

 

---

참고: https://blog.naver.com/ndb796/221240613074

29. 이분 매칭(Bipartite Matching)