[P4] 백준 1298번 노트북의 주인을 찾아서 C++ 이분 매칭

리뷰

 

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

n값이 작고 m값이 큰 이분매칭 문제

 

 

전역 변수

• N : 학생 배열의 최대 크기를 정의할 상수 변수
• M : 노트북 배열의 최대 크기를 정의할 상수 변수
• n : 학생의 수를 저장할 변수
• m : 노트북의 수를 저장할 변수
• ans : 정답을 저장할 변수
• mat : 노트북을 가진 학생의 번호를 저장할 배열
• v : 노트북을 참조한 시간을 저장할 배열
• t : 탐색 시간을 정의할 변수

 

함수

1. dfs

bool dfs(int node) {
	if (v[node] == t) return false;
	v[node] = t;
	
	for (int next : edges[node]) {
		if (!mat[next]) {
			mat[next] = node;
			return true;
		}
	}

	for (int next : edges[node]) {
		if (dfs(mat[next])) {
			mat[next] = node;
			return true;
		}
	}

	return false;
}

 

학생들이 노트북을 최대로 소유할 수 있는 경우를 찾는 함수

 

문제풀이

1. n, m에 값을 입력 받고, m개의 간선 정보를 edges벡터 배열에 추가해 준다.
2. 1~n번 학생을 순회하며 t를 증가시킨 후 dfs함수에 i를 전달하여 리턴값이 true라면 ans를 증가시킨다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

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

const int N = 101;
const int M = 5001;
int n, m, ans;
int mat[M];
int v[M];
int t;
vector<int> edges[N];

bool dfs(int node) {
	if (v[node] == t) return false;
	v[node] = t;
	
	for (int next : edges[node]) {
		if (!mat[next]) {
			mat[next] = node;
			return true;
		}
	}

	for (int next : edges[node]) {
		if (dfs(mat[next])) {
			mat[next] = node;
			return true;
		}
	}

	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b;
		edges[a].push_back(b);
	}

	for (int i = 1; i <= n; ++i) {
		t++;
		if (dfs(i)) ans++;
	}
	cout << ans;
}