백준 1298번: 노트북의 주인을 찾아서 (C++)

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

1298번: 노트북의 주인을 찾아서

---

Solved By:  Bipartite Matching

 

처음으로 이분 매칭 알고리즘을 사용했습니다. DFS의 리턴형이 bool인 함수를 구현하여 각 정점이 이어질 수 있는 지를 파악합니다. Time Complexity는 O(VE)입니다. 또 다른 이분 매칭 알고리즘들이 있다는데 알아보아야겠습니다.

 

처음 구현을 하여서 각 코드마다 어떤 역할인지 주석으로 달아두었습니다.

#include <iostream>
#include <vector>
#include <memory.h>
#define MAX 101
using namespace std;

int n, m;
vector<int> adj[MAX]; // 연결된 간선들 저장
bool visited[MAX]; //
int occupy[MAX]; // 어떠한 정점을 occupy(차지)하고 있는 정점의 정보

bool dfs(int node){
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        
        if(visited[next]) continue;
        // (biMatch는 실행될 때마다 visited가 memset에 의해 초기화된다)
        // 즉, biMatch가 실행되면서 위 조건에 의해 continue가 되는 경우는
        // 점유되어 있는 정점을 recursive call에 의해 건드렸다는 소리가 된다.
        // 하나의 점유 정점을 여러 개의 출발 정점에서 건드리는 것은
        // 이분 매칭의 의도에 엇나가므로 다음 조건이 필요하다.
        visited[next] = true;
        
        if(occupy[next] == 0 || dfs(occupy[next])){
        // 1. 현재 next vertex를 occupy하고 있는 정점이 없다
        // 2. 현재 next vertex를 occupy하고 있는 정점이
        // 다른 vertex로 갈 수 있다
            occupy[next] = node;
            return true;
        }
    }
    return false;
}

int main(){
    cin >> n >> m;
    
    int a, b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a].push_back(b);
    }
    
    int result = 0;
    for(int i = 1; i <= n; i++){
        memset(visited, false, sizeof(visited));
        if(dfs(i)) result++;
    }
    
    cout << result;
    return 0;
}