[백준] 2188 축사배정 , 11375 열혈강호, 9576 책 나눠주기 1298 노트북의 주인을 찾아서 +이분매칭
문제
농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.
첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.
농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.
입력
첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.
출력
첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.
유량문제와 비슷해 보이지만...(유량문제로도 풀 수는 있지만)
모든 간선의 capacity가 1이고, 소와 축사를 최대로 잇는 문제이므로
이분매칭을 사용합니다.
dfs 재귀로 풀긴했는데 이게 왜 정답이지? 라는 느낌...
열혈강호 1 문제와 동일합니다.
#include<bits/stdc++.h>
using namespace std;
int N, M;
vector<int>adj[201];
int arr[201], v[201];
bool dfs(int k) {
for (auto r : adj[k]) {
if (arr[r] == k || v[r])continue; //자기가 갖고있던 자리면 continue
v[r] = 1;
if (!arr[r]) { //주인없는 자리
arr[r] = k;
return true;
}
else if(dfs(arr[r])) { //이미 주인이 있으면, 자리가 있으면
arr[r] = k;
return true;
}
}//자리가 없으면
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, x;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> n;
while (n--) {
cin >> x;
adj[i].push_back(x);
}
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
memset(v, 0, sizeof(v));
if (dfs(i))cnt++;
}
cout << cnt;
}사실 이분매칭이라고 쓰지만 그냥 단순히 세는 방법입니다.
1번 소가 한 자리를 차지했을때,
만약 3번 소가 1번소의 자리가 갖고싶으면 1번소가 비켜주고 들어갈 수 있는 다른자리에 들어가면 됩니다.
1번부터 N번소까지 재귀를 통해 구석에 구석까지 비켜주고 최대한 앉는다면
그게 정답입니다.
이때 무한루프가 발생할 수 있으므로,,,, 방문처리를 해주면 무한으로 돌지 않습니다.
11376 열혈강호 2
문제
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.
각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.
각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.
출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.
#include<bits/stdc++.h>
using namespace std;
int N, M, v[1001], work[1001];
vector<int>adj[1001];
bool dfs(int k) { //k번째 사람 , n: 0 ,1 adj[k][0]= k가 할 수있는 일 1, adj[k][1]=k가 할 수 있는일2
for (auto r : adj[k]) {
if (v[r] )continue; //내가하던거나 이미 방문햇으면 contiue
v[r] = 1;
if (!work[r]) { //r번째 일을 아무도 안하면 내가할게
work[r] = k;
return true;
}
if (dfs(work[r])) { //r번째일 하던사람이 다른거하러가면 내가함
work[r] = k;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
int n, a;
for (int i = 1; i <= N; i++) {
cin >> n;
while (n--) {
cin >> a;
adj[i].push_back(a);
}
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 2; j++) {
memset(v, 0, sizeof(v));
if (dfs(i))cnt++;
}
}
cout << cnt;
}열혈강호 1 문제와 다른점은 한 사람이 두가지의 일을 할 수 있다는 점입니다.
따라서, 한 사람에대해 두번씩 루프를 돌아야 합니다.
>>루프를 두번 돌때, 똑같은 일에 대해서 두번 일해서, 서로 다른일을 안할까 순간 생각을 했는데,
방문표시를 하므로 두번째 루프에서 이미 한 일에대해 똑같은 재귀를 돌게 됩니다. 이때 방문표시를 확인하고 다음 일에대해 처리를 하므로, 모든 상황에 대해 타당합니다.
9576 책 나눠주기
문제
백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 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)
출력
각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int > pi;
int tc, N, M, a, b, v[1001];
pi adj[1001];
int book[1001];
bool dfs(int k) {
auto [from, to] = adj[k];
for (int i = from; i <= to; i++) {
if (v[i] || book[i]==k )continue; //이미 방문했거나, 자기책이라면 continue;
v[i] = 1;
if (!book[i]) { //만약 i번째 책의 주인이 없다면
book[i] = k; //이 책은 이제 제겁니다
return true;
}
if (dfs(book[i])) { //만약 책의 주인이 있고, 책주인이 다른책을 가져갔다면
book[i] = k; //이 책은 이제 제겁니다
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tc;
while (tc--) {
cin >> N >> M;
memset(book, 0, sizeof(book));
memset(adj, 0, sizeof(adj));
for (int i = 1; i <= M; i++) {
cin >> a >> b;
adj[i] = { a,b };
}
int cnt = 0;
for (int i = 1; i <= M; i++) {
memset(v, 0, sizeof(v));
if (dfs(i))cnt++;
}
cout << cnt << "\n";
}
}a부터 b까지를 pair에 저장합니다. 이후 이분매칭... 동일합니다.
1298 노트북의 주인을 찾아서
문제
어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 받을 수 있었지만, 애석하게도 N명의 학생들이 정확히 자신의 노트북이 어떤것인지 알지 못했다. 왜냐하면 그들은 노트북을 구입한게 바로 어제였기 때문이다.
어차피 새것인 노트북, 바뀐들 어떠하랴.
그들에게 자신의 노트북이라고 생각되는 노트북들을 얘기해 보라고 했다.
이번에는 정말 신기하게도 그들 각각이 노트북을 여러개 선택한 것이었다! “이것 아니면 이것 아니면 이것 아니면 이것 일거 같아요”라카더라.
우리의 목적은 이들의 요구를 가장 많이 만족시키는 것이다.
요컨대, 자신이 자신의 것 같다라고 얘기한 노트북을 갖는 사람을 최대화 하라는 소리다.
입력
첫째 줄에는 노트북이 섞인 날 어제 노트북을 구입한 사람의 수 N(1 ≤ N ≤ 100)과 노트북 예상의 개수 M(0 ≤ M ≤ 5,000) 주어진다.
둘쨋줄에서 M+1번째 줄 까지는 각각 한 줄마다 a b가 주어지는데, 이는 a번 사람이 b번 노트북을 자신의 것이라고 생각한다는 의미를 갖는다.
노트북과 사람의 번호는 1보다 크거나 같고, N보다 작거나 같다. 두 사람 또는 두 노트북이 같은 번호를 갖는 경우는 없다.
출력
최대로 만족될 수 있는 사람 수를 출력한다.
#include<bits/stdc++.h>
using namespace std;
int N, M, v[5001], notebook[5001], ans;
vector<int>adj[101];
bool dfs(int k) {
for (auto r : adj[k]) {
if (v[r] )continue;
v[r] = 1;
if (!notebook[r]) {
notebook[r] = k;
return true;
}
if (dfs(notebook[r])) {
notebook[r] = k;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
int a, b;
while (M--) {
cin >> a >> b;
adj[a].push_back(b);
}
for (int i = 1; i <= N; i++) {
memset(v, 0, sizeof(v));
if (dfs(i))ans++;
}
cout << ans;
}