BOJ 1444번 숌 언어

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

하나의 단어는 알파벳 소문자하나와 대문자 하나로 이루어진다. 소문자가 앞에 나오는 경우와 뒤에 나오는 경우

이렇게 두가지 경우가 있다. 알파벳 소문자와 대문자가 번갈아 나오는 문장이 입력으로 들어올 때

이 문장은 몇 개의 단어로 이루어 질 것이다. 이 때 여러가지 케이스가 있을 텐데 그중 최소 단어 개수를 찾는 문제이다.

예를 들어 aAbAc 가 있으면 aA, bB, Ac 로 이루어 졌을 수도 있고 aA, Ab, Ac 로 이루어 졌을 수도 있는 것이다.

이 문제는 결국 최소 정점 덮개 이다. 최소 정점 덮개란 이분 그래프에서 모든 간선이 자신과 접한 두 정점 중

최소한 하나는 선택하도록 할 때 최소로 선택하는 정점의 수이다. 그니까 하나의 정점을 선택하면 그와 인접한

간선들을 덮는 것과 같다고 생각할 수 있어서 최소 정점 덮개이다.(Minimum Vertex Cover)

쾨닉의 정리에 의해 최대 매칭과 동치라는 것이 증명 되어있다.

그렇다면 왜 최소 정점 덮개일까? 개념적으로 이해 해보자.

우리는 문자열에 존재하는 각각의 알파벳이 특정 단어에 속하도록 해야 한다. 그니까 각 알파벳을

단어들로 커버해야한다는 것이다.  결국 단어는 정점이 되고, 알파벳은 간선이 된다. 단어로 알파벳을

덮는 것이니 말이다. 그렇기 때문에 하나의 알파벳은 두개의 단어중 하나로 덮을 수 있기 떄문에

최소 정점 덮개 모델에서 하나의 간선을 양쪽의 두 정점중 하나로 덮을 수 있다는 것과 일치한다는 점에서

하나의 알파벳을 공유하는 두 단어를 간선으로 이어주면 된다. 이말은 결국 하나의 알파벳을 공유하는 두 단어 중

하나는 무조건 대문자가 앞에오고 하나는 뒤에올 것이기 때문에 간선으로 연결되는 두 정점 중 하나는 

대문자가 앞, 하나는 대문자가 뒤, 즉 이분 그래프를 구성할 수가 있다. 왼쪽 컴포넌트 원소는 (소+대) 단어들로,

오른쪽 컴포넌트는 (대+소) 단어들로 구성하여 이분 그래프를 형성한뒤 최대매칭을 구하면된다.

여기서 주의할 점이 한가지 있다. 맨왼쪽에있는 알파벳과 맨오른쪽에 있는 알파벳은 예외적으로 두 단어에 의해

커버될 수 있는것이 아님을 주목하자. 맨 왼쪽에 있는 알파벳은 무조건 맨 왼쪽에 있는 단어에 의해서만 커버될 수 있고

반대도 마찬가지 이기 때문에 양끝에있는 단어는 무조건 선택해야한다. 그렇기 때문에 처음에 이분그래프를

구성하기 전에 양끝에있는 단어는 답에 미리 누적시켜놓고 간선을 이어 줄 때에 양끝에 있는 단어중 하나라도

이 양끝에 있는 단어라면 간선을 이어주지 않는다. 왜냐하면 이미 그 단어를 선택했으며 그렇기 때문에 그 단어(정점)과

인접한 모든 간선은 덮어져있는 상태이기 때문에 감안할 필요가 없어져서 아예 없다고 보고 구해야 하기 때문이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
map<string,int> num[2];
int cnt[2];
map<string,int> already;
string S;
int ans;
int aMatch[1503], bMatch[1503];
int iter[1503];
int level[1503];
vector<int> G[1503];
int cntA, cntB;
int check[1503][1503];
bool isUpper(char c){
    return 'A' <= c && c <= 'Z';
}
void bfs(){
    queue<int> q;
    for(int a = 0 ; a < cntA; a++) if(aMatch[a] == -1) q.push(a), level[a] = 0;
    while(!q.empty()){
        int a = q.front();
        q.pop();
        for(int b : G[a]){
            if(bMatch[b] == -1 || level[bMatch[b]] != -1) continue;
            level[bMatch[b]] = level[a] + 1;
            q.push(bMatch[b]);
        }
    }
}
bool dfs(int a){
    for(int& i = iter[a]; i < (int)G[a].size(); i++){
        int b = G[a][i];
 
        if(bMatch[b] == -1 || (level[bMatch[b]] == level[a] + 1 && dfs(bMatch[b]))){
            aMatch[a] = b;
            bMatch[b] = a;
            return true;    
        }
    }
    return false;
}
int hopcroft(){
    int ret = 0;
    while(1){
        memset(level,-1,sizeof(level));
        memset(iter,0,sizeof(iter));
        bfs();
        int add = 0;
        for(int a = 0 ; a < cntA; a++) if(level[a] == 0 && dfs(a)) add++;
        if(!add) break;
        ret += add;
    }
    return ret;
}
int main() {
    memset(aMatch,-1,sizeof(aMatch));
    memset(bMatch,-1,sizeof(bMatch));
    cin >> S;
    for(int i = 0 ; i < (int)S.size()-1; i++){
        string tmp = S.substr(i,2);
        int id = isUpper(tmp[0]);
        if(!num[id][tmp]) num[id][tmp] = ++cnt[id]; 
        if(i == 0 || i == (int)S.size()-2) {
            if(already[tmp] == 0) ans++, already[tmp] = 1;
        }
    }
 
    for(int i = 0 ; i < (int)S.size()-2; i++){
        string s1 = S.substr(i,2);
        string s2 = S.substr(i+1,2);
        if(already[s1] || already[s2]) continue;
        if(isUpper(s1[0])) swap(s1,s2);
        int id = isUpper(s1[0]);
        int u = num[id][s1]-1;
        int v = num[!id][s2]-1;
        if(check[u][v] == 0) check[u][v] = 1, G[u].push_back(v);
    }
 
    if(cnt[0] == 0 || cnt[1] == 0) return !printf("%d\n",ans);
    cntA = cnt[0], cntB = cnt[1];
    ans += hopcroft();
    cout << ans;
 
 
    return 0;
}