[백준] 9576번: 책 나눠주기

문제 링크: [백준] 9576번: 책 나눠주기

20년의 마지막 주말 잘 보내셨나요?

연말에 즐거운 시간 보내시고 술은 적당히 먹는게 좋겠습니다..

같이 문제 풀어볼까요?

.

문제

---

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입출력

---

입력 : 첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력 : 각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

풀이 & 코드

---

학부생 과 전공책 집단간의 최대 매칭을 찾는 문제이기때문에 이분매칭 알고리즘을 사용하였습니다. 두 집단간의 그래프 연결 관계는 입력된 a , b 사이의 모든 책과 연결되어 있고 이 정보를 2차원 배열을 통해 저장하였습니다. 

이분매칭 알고리즘에 대해서는 따로 포스팅을 남기도록 하겠습니다!

#include<bits/stdc++.h>
using namespace std;
const int MAX=1000+1;
int T,N,M,students[MAX][3],books[MAX],visited[MAX];

bool dfs(int a){
	if(visited[a]) return false;
	visited[a]=true;
	for(int b=students[a][1];b<=students[a][2];b++){
		if(books[b]==0||dfs(books[b])){		// 매칭이 안되어 있는 경우,
			students[a][0]=b;               // books[b] == 0 -> 학생인덱스 1부터 시작
			books[b]=a;
			return true;
		}
	}
	return false;
}

int biMatch(){
	int ans=0;
	for(int i=1;i<=M;i++){
		fill(visited,visited+MAX,0);
		if(dfs(i)) ans++;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--){
		
		memset(students,0,sizeof(students));
		memset(books,0,sizeof(books));

		cin>>N>>M;
		for(int i=1;i<=M;i++){
			cin>>students[i][1]>>students[i][2];     //  a , b입력
		}
		cout<<biMatch()<<"\n";
	}
	return 0;
}

부족한 부분이나 궁금한 부분 댓글 감사하겠습니다!.