[백준 22742번] Make Friendships

문제 링크

https://www.acmicpc.net/problem/22742

 

문제 요약

이팍이는 파티에서 여러 여자친구를 새롭게 사귀었고, 이들과 데이트 일정을 잡으려고 한다. 이삭이는 한 번에 한 명의 여자친구만 만날 수 있으며, 만날 수 있는 시간은 정해져 있다. 또한 각 여자친구마다 이삭이를 만날 수 있는 시간이 정해져 있다. 이 때 이삭이가 최적의 일정으로 스케줄링을 했을 때 최대한 만날 수 있는 여자친구들의 수를 구하는 문제이다.

 

문제 풀이

이삭이가 사용할 수 있는 시간들을 왼쪽 노드로, 각 여자친구들을 오른쪽 노드로 설정하면 문제를 이분 그래프로 모델링 할 수 있다. 아래 그림은 예제 입력을 이분 그래프로 모델링 한 결과이다.

 

이분 그래프로 모델링 한 예제입력

이제 문제는 이분 그래프에서 최대 매칭을 구하는 문제로 바뀌었고, 이분 매칭 알고리즘을 이용해 문제를 풀 수 있다.

 

그래프를 구현할 때에는 이삭이가 가능한 시간들에 Map과 같은 자료구조를 이용해서 인덱스를 기록해 놓는다. 그런 다음 여자친구들이 이삭이를 만날 수 있는 시간들이 Map에 있는지 확인을 한 뒤, 해당 시간이 Map에 존재하면 간선을 연결하여 이분 그래프를 구성한다.

 

소스 코드

#include <stdio.h>
#include <vector>
#include <map>

using namespace std;

vector<int> matched;
vector<bool> visited;
vector<vector<int>> node;

// n: 왼쪽 노드의 수
void init(int n) {
    matched.assign(n, -1);;
    visited.assign(n, false);
    node.assign(n, vector<int>());
}

// DFS를 이용해 최대 매칭을 찾는 함수
bool dfs(int here) {
    if (visited[here]) {
        return false;
    }
    
    visited[here] = true;
    
    for (int there: node[here]) {
        if (matched[there] == -1 || dfs(matched[there])) {
            matched[there] = here;
            
            return true;
        }
    }
    
    return false;
}

int main() {
    int m;
    
    // 오른쪽 노드의 수를 입력 받음(이삭이가 사귄 여자친구들의 수)
    while (scanf("%d", &m) && m) {
        int n, t, x;
        
        // 시간과 왼쪽 노드 인덱스를 매핑하는 해시맵
        map<int, int> hash;
        
        // 왼쪽 노드의 수를 입력 받음(이삭이가 가능한 시간)
        scanf("%d", &n);
        for (int i = 0 ; i < n ; ++i) {
            scanf("%d", &x);
            hash[x] = i;
        }
        
        init(n);
        
        for (int i = 0 ; i < m ; ++i) {
            scanf("%d", &t);
            
            while (t--) {
                scanf("%d", &x);
                
                // 입력된 시간이 해시맵에 존재하면
                if (hash.count(x)) {
                    // 왼쪽 노드에 오른쪽 노드 번호를 연결
                    node[hash[x]].push_back(i);
                }
            }
        }
        
        int ans = 0;
        
        for (int i = 0 ; i < n ; ++i) {
            visited.assign(n, false);
            
            if (dfs(i)) {
                ++ans;
            }
        }
        
        printf("%d\n", ans);
    }
}