백준 17481 - 최애 정하기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17481

17481번: 최애 정하기

이분 매칭으로 쉽게 풀 수 있는 문제입니다.

이분 그래프에서 두 그룹을 X, Y그룹이라고 할 때, 모든 경로의 방향이  X -> Y인 그래프의 최대 유량을 구하는 것이 이분 매칭입니다. 

문제에서 볼 수 있듯이, 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 

이때 매칭한다는 것은 1대 1함수와 같이 하나의 정점이 다른 그룹의 하나의 정점만을 점유하고 있는 상태를 말합니다.

 

이분 매칭을 구성하는 핵심 코드입니다.

bool dfs(int start){
    if(check[start]) return false;
    check[start] = true;
    for(int i = 0; i < Match[start].size(); i++){
        int x = Match[start][i];
        if(b_match[x] == -1 || dfs(b_match[x])){
            a_match[start] = x;
            b_match[x] = start;
            return true;
        }
    }
    return false;
}

start에는 1 부터 N까지, 한 그룹의 정점이 순서대로 입력됩니다.

check 배열을 통해, 찾으려는 정점이 이전에 다른 점과 연결되어 있는지를 확인합니다. 

자신과 연결된 정점을 연결하는 과정에서,

 

1. 내가 매칭하려는 점이 다른 점과 연결이 되어있나?

2. 매칭하려는 점과 연결된 정점이 다른 정점과 연결될 수 있나? 

 

두 가지를 확인합니다. 2번을 확인하는 이유는 순서대로 정점을 탐색하기 때문에, 현재 매칭하려는 점이 다른 점과 연결되어 있다면 현재 정점보다 앞의 순서일 것입니다. 앞 순서의 정점을 다른 점에 다시 매칭할 수 있다면, 현재 정점을 이을 수 있음으로 더 많을 수를 매칭할 수 있게 됩니다. 

두 조건 중 하나만 만족한다면, 정점들을 매칭해줍니다. 

 

해당 DFS 과정을 1~N번 정점까지 넣어주면서 확인합니다. 그 과정에서 더이상 매칭할 수 없는 경우가 있을 것 입니다.

1. 자신보다 앞선 정점을 다른 정점과 매칭할 수 없는 경우

2. 더 이상 정점을 매칭할 수 없는 경우

해당 경우에는 DFS가 true의 값을 return하지 못함으로 이분 매칭이 끝나게 됩니다.

 

마지막에 Size를 출력하면서 최대 매칭 수를 구해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#define INF 987654321

using namespace std;

int N, M;
string name[1011];
vector<int> Match[1011];
vector<int> a_match, b_match;
bool check[1011];

int name_order(string x){
    for(int i = 1; i <= M; i++){
        if(name[i] == x) return i;
    }
}

bool dfs(int start){
    if(check[start]) return false;
    check[start] = true;
    for(int i = 0; i < Match[start].size(); i++){
        int x = Match[start][i];
        if(b_match[x] == -1 || dfs(b_match[x])){
            a_match[start] = x;
            b_match[x] = start;
            return true;
        }
    }
    return false;
}

void solve(){
    a_match = vector<int>(N+1, -1);
    b_match = vector<int>(M+1, -1);
    int size = 0;
    for(int i = 1; i <= N; i++){
        memset(check, false, sizeof(check));
        if(dfs(i)) size++;
    }
    if(size == N) cout << "YES";
    else cout << "NO" << "\n" << size;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> name[i];
    }
    for(int i = 1; i <= N; i++){
        int x;
        cin >> x;
        for(int j = 1; j <= x; j++){
            string y;
            cin >> y;
            Match[i].push_back(name_order(y));
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요