[C++] 백준 1298번 노트북의 주인을 찾아서

이분 매칭으로 문제를 해결했습니다.

노트북과 사람을 매칭해줄 때 가장 많이 매칭한 경우 매칭한 수를 출력하는 문제입니다.

1. 원하는 노트북 탐색
2. 원하는 노트북이 비어 있다면 매칭
3. 원하는 노트북이 비어 있지 않다면 그 노트북과 매칭된 사람이 1. 으로 이동 (이 때 탐색된 노트북은 체크되서 루프 X)
4. 3번에서 원래 매칭된 주인이 다른 노트북으로 선택이 가능한 경우, 현재 노트북과 매칭
5. 3번에서 원래 매칭된 주인이 다른 노트북으로 선택이 불가능한 경우, 1. 으로 이동
6. 현재 사람이 노트북 매칭에 성공했다면 카운트 증가, 그렇지 않다면 다음 사람으로

위와 같은 순서로 동작합니다.
비어있다면 넣어주고, 비어있지 않다면 밀어내는 방식입니다.

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int N, M;
int num;
int people;
int want[110];
bool visit[110];
vector<int> v[110];

bool solve(int x)
{
	for (int i = 0; i < v[x].size(); ++i) {
		int index = v[x][i];
		
		if (visit[index]) {
			continue;
		}
		visit[index] = true;

		if (want[index] == 0 || solve(want[index])) {
			want[index] = x; 
			return true;
		}
	}
	return false;
}

int main() 
{
	int count = 0;

	cin >> N >> M;

	memset(want, 0, sizeof(want));

	for (int i = 0; i < M; ++i) {
		cin >> people;
		cin >> num;
		v[people].push_back(num);
	}

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

	cout << count << endl;

	return 0;
}