[C++] 16590번 KMP

 

 

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

---

 

25/12/13

 

 

이분 매칭 문제이다. 그래프 모델링을 잘 해보자.

---

 

문제 접근 방식:

 

 

문제를 요약하면 다음과 같다.

 

이름 N개가 주어지고, 문자열 쿼리가 주어질 때 마다, 이름의 이니셜을 최대 사람 당 한 번씩 사용하여 해당 문자열을 만들 수 있다면 YES, 아니면 NO를 출력하면 된다.

 

예를 들어, Donald Knuth, Vaughan Pratt, James Hiram Morris 세 이름이 주어졌으면, KMP는 YES이다. (Knuth, Morris, Pratt 이므로)

 

최대 유량을 사용해도 되고 이분 매칭을 해도 좋으나, 그래프 모델링은 거의 유사하다.

 

예제 입력 1과 2의 그래프 모델링은 다음과 같다.

 

 

따라서 사람의 이니셜을 모두 따와서 하나의 set으로 묶은 다음, 그 set을 하나의 노드로 취급하여 구현하면 된다.

 

매 문자열 쿼리마다 이분 매칭을 진행하도록 하자.

 

입력시에 줄 단위로 입력이 이뤄지므로 getline을 사용하여 입력 받고, set과 find를 사용하여 쉽게 구현할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 16590번 KMP
// 이분 매칭
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

struct Kuhn{
    int L, R;
    vector<vector<int>> adj;
    vector<int> visited, matchedR;
    Kuhn(int L, int R) : L(L), R(R), adj(L), visited(R, 0), matchedR(R, -1) {};
    void addEdge(int u, int v){adj[u].push_back(v);}
    int dfs(int u){
        for (int v : adj[u]){
            if (!visited[v]){
                visited[v] = 1;
                if (matchedR[v] == -1 || dfs(matchedR[v])){
                    matchedR[v] = u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int matching(void){
        int match = 0;
        for (int u = 0; u < L; ++u){
            fill(visited.begin(), visited.end(), 0);
            if (dfs(u)) ++match;
        }
        return match;
    }
};

int main(void){
    fastio

    int N, Q; cin >> N >> Q; cin.ignore();
    vector<string> name(N);
    vector<set<char>> nameUpper(N);
    for (int i = 0; i < N; ++i){
        getline(cin, name[i]);
        for (char ch : name[i]){
            if ('A' <= ch && ch <= 'Z'){
                nameUpper[i].insert(ch);
            }
        }
    }
    while (Q--){
        string S; cin >> S;
        int M = S.size();
        Kuhn kuhn(N, M);
        for (int u = 0; u < N; ++u){
            for (int v = 0; v < M; ++v){
                if (nameUpper[u].find(S[v]) != nameUpper[u].end()){
                    kuhn.addEdge(u, v);
                }
            }
        }
        if (kuhn.matching() != M) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}