백준)2188-축사 배정

문제 링크 : https://www.acmicpc.net/problem/2188

2188번: 축사 배정

문제

농부 John 씨는 그의 소 축사를 갓 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, John 씨는 축사를 N개의 칸으로 구분하여 두고, 한 칸에는 한 마리의 소만을 들어가도록 하였다.

첫 주에는 소들을 임의적으로 칸에 배정하여 축사를 운영하였으나, 곧 문제가 발생하게 되었다. 자신들이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

농부 John 씨를 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다고 한다.

입력

첫째 줄에 소의 마릿수 N과 축사의 개수 M이 주어진다. (1 <=N <=200, 1 <=M <=200)

둘째 줄부터 N개의 줄에는 N마리의 소들이 각자 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si(0 <=Si <=M)가 먼저 주어지고, 그 이후에 Si개의 축사 번호가 주어진다. 한 축사가 2번 이상 입력되는 경우는 없다.

출력

첫째 줄에 축사에 들어갈 수 있는 소 마릿수의 최댓값을 출력한다.

풀이

소들이 원하는 축사가 이므로 최대한 소들을 배려해주어야 한다. 예를 들어 A 소는  1 , 2 축사를 가고 싶어 하고 B소는 1번 축사만 가고 싶어 한다고 생각해보자. 만약 A가 먼저 1번 축사에 배정받고 다음 B 소 차례가 되었다. B소는 2번 축소를 가고 싶어 하지 않기 때문에 2번 숙소도 좋아하는 소가 양보를 해주어야 한다. 이런 상황을 DFS를 이용하여 구현하였다. 매 순환을 하면서 d 배열에 소가 들어가 있는 축사 번호를 넣어 준다. 매 순환하면서 방문 표시 도 필수로 해주자!

 

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
 
int d[201];
int visited[201];
vector<int> a[201];
 
int dfs(int x) {
    int i;
 
        for( i = 0 ; i< a[x].size() ; i++) {
            int y = a[x][i]; 
 
                if(visited[y]) continue; 
 
                    visited[y] = 1 ;
 
                if(d[y] == 0 || dfs(d[y]) ) {
                            d[y] = x ;
 
                            return 1;
                }
        }
 
    return 0;
}
 
 
int main()
{
    int i,j;
    int N , M;
    cin >> N >> M;
 
    for( i=1 ; i<= N ;i++) {
        int s;    cin >> s;
        
            for(j=1 ; j<=s; j++) {
                int q; cin >> q;
                a[i].push_back(q);
            }
 
    }
 
int ans = 0 ;
 
for(i=1; i<=N ; i++) {
    
    memset(visited,0,sizeof(visited));
 
    if(dfs(i))
        ans++;
}
 
cout << ans;
 
    return 0;
}