[BOJ] 2188 : 축사 배정
💉문제 내용
💉입출력
🧺입력
첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.
🧺출력
첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.
🔋예제 입출력
🔮예제 입력
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
🔮예제 출력
4
💉문제 분석
🔋분류
네트워크유량, 최대유량, 이분매칭
🔋난이도
플래티넘IV
💉문제 풀이
🔋해법
🧺입력
첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.
🧺출력
첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.
🔮예제 입력
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
🔮예제 출력
4
🔋분류
네트워크유량, 최대유량, 이분매칭
🔋난이도
플래티넘IV
💉문제 풀이
🔋해법
일반적인 이분매칭문제입니다.
딱히 주의할것은없습니다.
🔋소스코드
#include <bits/stdc++.h>
//Static variables
constexpr int MAX = 201;
constexpr int INF = 987654321;
//AlgoCapsule
class AlgoCapsule {
public:
void Run() {
Input();
Solve();
Output();
}
void Input() {
std::cin >> N >> M;
for (int i = 1; i <= N; ++i) {
int T;
std::cin >> T;
for (int k = 0; k < T; ++k) {
int a;
std::cin >> a;
adj[i].push_back(a);
}
}
}
void Solve() {
for (int i = 1; i <= N; i++) {
std::fill(visit, visit + MAX, false);
if (BipartiteMatching(i)) count++;
}
}
void Output() {
std::cout << count;
}
bool BipartiteMatching(int start) {
for (int i = 0; i < adj[start].size(); ++i) {
int x = adj[start][i];
if (visit[x]) continue;
visit[x] = true;
if (d[x] == 0 || BipartiteMatching(d[x])) {
d[x] = start;
return true;
}
}
return false;
}
AlgoCapsule() { }
private:
bool visit[MAX];
int d[MAX];
std::vector<int> adj[MAX];
int N, M, count = 0;
};
//Module Entry
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
AlgoCapsule AC;
AC.Run();
return 0;
}
이번에는 처음으로 저가 만든 알고리즘 문제풀이용 기본소스코드를 사용했습니다.
알고리즘 문제풀이용 기본 소스코드 보러가기
이분매칭문제는 많이 안풀어봐서, 이분매칭문제 처음 푸시는분들에게는 초반 손풀기용으로 괜찮은 문제같습니다.
💉마치며...
궁금한 부분있으시면 댓글로 질문주세요~
Author And Source
이 문제에 관하여([BOJ] 2188 : 축사 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dpmawile/boj2188저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)