[백준] 9576번 책 나눠주기 C++ 문제풀이

문제 풀이

이번 소마 1차 코테 4번 문제를 시간이 부족해 못풀었는데, 오픈채팅방에서 이분매칭이라는 알고리즘 관련된 문제라고 해서 이분매칭에 대해 공부도 할 겸 풀어보았다.

"이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘입니다." - 나동빈

각 사람이 원하는 항목이 정해져 있을 때 모든 사람 각각이 원하는 항목을 하나씩 선택하여 가장 많이 연결되는 경우를 찾는 문제입니다.

위와 같이 A라는 집단에서 B라는 집단의 항목들에 대한 선호도가 있을 때, 어떻게 해야 A집단과 B집단을 연결할 수 있을까를 푸는 문제라고 생각하면 된다..

1번 사람 연결 진행

문제를 푸는 방식은 맨 위의 사람부터 오른쪽 물건에 대해 연결한다

2번 사람까지 연결 진행

그리고 2번째 사람이 연결을 하려는데 1번 사람이 1번 물건을 점유하고 있으므로 1번에게 다른 점유할 곳이 없는지 물어봐야한다.

그러면 1번 사람이 2번째 물건으로 연결 대상을 변경할 수 있으므로 True를 반환하고 1번 사람 -> 2번 물건 , 2번 사람 -> 1번 물건을 점유하게 된다.

이런식으로 쭉쭉 연결해서 최대 매칭 수를 구하면 되는 문제이다

연결 대상을 변경할 수 있는지 문의하는 과정을 확인해보자

vector<int> per[1002]; //어떤 사람이 어떤 책을 선호하는지 저장 
			//1번 사람이 1, 2, 3번 책을 선호한다고 가정
                       // per[1] = {1,2,3}이 저장됨.
int nd[1002]; // 책을 어떤 사람이 점유 했는지! 저장
bool c[1002]; //책이 점유 되었는지

bool dfs(int x) {
	for (int i = 0; i < per[x].size(); i++) {
		int t = per[x][i];
		if (c[t] == true) 
			continue;
		c[t] = true;
		if (nd[t] == 0 || dfs(nd[t])) { //책을 점유한 사람이 없거나 / 점유한 사람이 다른 책을 선택할 수 있는 경우
			nd[t] = x;
			return true;
		}
	}
	return false;
}

이 문제에서 핵심은 dfs함수 안의 if(nd[t] == 0 || dfs(nd[t])) 부분이다!

nd[t] == 0 : 책을 점유한 사람이 없는 경우 책을 x라는 사람이 점유

dfs(nd[t]) : 책을 점유한 사람이 있는 경우 이 책 말고 다른 책을 점유할 수 있는지 문의 

 

위의 bool dfs(int x ) 함수를 통해 이분 매칭을 수행할 수 있다!

소스 코드

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

vector<int> per[1002];
int nd[1002]; // 책을 어떤 사람이 점유 했는지! 저장
bool c[1002]; //책이 점유 되었는지

bool dfs(int x) {
	for (int i = 0; i < per[x].size(); i++) {
		int t = per[x][i];
		if (c[t] == true) 
			continue;
		c[t] = true;
		if (nd[t] == 0 || dfs(nd[t])) {
			nd[t] = x;
			return true;
		}
	}
	return false;
}

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, m;
		cin >> n >> m;

		for (int j = 1; j <= m; j++) {
			int a, b;
			cin >> a >> b;
			for (int t = a; t <= b; t++) {
				per[j].push_back(t);
			}
		}
		fill(nd, nd + 1001, 0);
		int ans = 0;

		for (int j = 1; j <= m; j++)
		{
			fill(c, c + 1001, false);
			if (dfs(j)) 
				ans++;
		}
		cout << ans << '\n';

		for (int t = 1; t <= m; t++) {
			per[t].clear();
		}
	}
	return 0;

}