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

✏️문제 링크

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

1298번: 노트북의 주인을 찾아서

 

✏️문제 설명

 

 

✏️문제 풀이

기본적인 이분 매칭 알고리즘을 구현하는 문제입니다.

https://pooreumjung.tistory.com/338

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

 

✏️문제 코드

#include<iostream>
#include<vector>
using namespace std;
#define MAX 101

int N, M;
vector<int>graph[MAX];
int node[MAX];
bool visit[MAX];
bool dfs(int person);
int main() {

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

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int per, com;
		cin >> per >> com;
		graph[per].push_back(com);
	}

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

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