이분 매칭 알고리즘 어려운 문제들 풀이 (Platinum II ~ Diamond)

백준 BOJ 3419번 : Racing Car Trail

문제 난이도 : Diamond III

알고리즘 분류 : 이분 매칭

 

N x M 크기의 배열이 주어지고, X가 없는 칸에서만 이동이 가능하다고 할 때, Alice와 Bob이 번갈아가면서 지나온 칸은 다시 이동하지 않도록 칸을 이동시키면서 상대가 더 이상 이동하지 못하도록 최선의 전략으로 이동시킨다고 할 때, 각 칸에서 시작할 때 누가 이기는지를 구하는 문제이다.

 

격자 그래프는 이분 그래프이므로 이분 매칭 알고리즘으로 최대 매칭을 구한 뒤, 시작점 v를 포함하지 않는 최대 매칭이 존재한다면 Bob이 항상 이길 수 있다.

왜냐하면 그러한 매칭이 존재하는 경우 Alice는 어떻게 이동해도 최대 매칭에 포함되는 정점으로 이동하게 되고, Bob은 그 격자점과 매칭되어있는 점을 따라서만 이동시키면 되기 때문이다.

만약 그러한 매칭이 존재하지 않는 경우 이번에는 Alice가 격자점과 매칭되어있는 점을 따라서 이동시키면 승리하게 된다.

 

N x M 모든 격자에 대해 그래프 연결을 다시 수행한 뒤 이분 매칭을 각각 돌리면 시간 초과가 발생하므로, 삭제한 뒤 새로 매칭을 찾는 격자점 한 칸에 대해서만 이분 매칭을 수행해주면 시간 초과를 피해 AC를 받을 수 있다.

 

 

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj1, adj2;
vector<int> l1, r1, l2, r2;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj1[x].size(); i++) {
        int y = adj1[x][i];

        if(r1[y] == -1 || (!vis[r1[y]] && f(r1[y]))) {
            l1[x] = y, r1[y] = x;

            return true;
        }
    }

    return false;
}

bool g(int x) {
    vis[x] = true;

    for(int i=0; i<adj2[x].size(); i++) {
        int y = adj2[x][i];

        if(r2[y] == -1 || (!vis[r2[y]] && g(r2[y]))) {
            l2[x] = y, r2[y] = x;

            return true;
        }
    }

    return false;
}

vector<vector<int>> tadj;
vector<int> ll, rr;

bool h(int x) {
    vis[x] = true;

    for(int i=0; i<tadj[x].size(); i++) {
        int y = tadj[x][i];

        if(rr[y] == -1 || (!vis[rr[y]] && h(rr[y]))) {
            ll[x] = y, rr[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N, M; cin >> N >> M;
        if(N == 0 && M == 0) break;

        vector<vector<char>> v(N+1, vector<char>(M+1));

        for(int i=1; i<=N; i++)
            for(int j=1; j<=M; j++) cin >> v[i][j];

        int s = (N*M + 1) / 2;

        int di[4] = {1, -1, 0, 0};
        int dj[4] = {0, 0, 1, -1};

        adj1.clear();
        adj1.resize(s+1);

        for(int i=1; i<=N; i++)
            for(int j=!(i%2)+1; j<=M; j+=2) {
                if(v[i][j] != '.') continue;

                for(int k=0; k<4; k++) {
                    int ni = i + di[k];
                    int nj = j + dj[k];

                    if(ni < 1 || nj < 1 || ni > N || nj > M) continue;
                    if(v[ni][nj] != '.') continue;

                    adj1[((i-1)*M+j+1)/2].push_back(((ni-1)*M+nj+1)/2);
                }
            }

        l1.clear();
        l1.resize(s+1, -1);

        r1.clear();
        r1.resize(s+1, -1);

        for(int i=1; i<=s; i++) {
            vis.clear();
            vis.resize(s+1);

            f(i);
        }

        adj2.clear();
        adj2.resize(s+1);

        for(int i=1; i<=N; i++)
            for(int j=(i%2)+1; j<=M; j+=2) {
                if(v[i][j] != '.') continue;

                for(int k=0; k<4; k++) {
                    int ni = i + di[k];
                    int nj = j + dj[k];

                    if(ni < 1 || nj < 1 || ni > N || nj > M) continue;
                    if(v[ni][nj] != '.') continue;

                    adj2[((i-1)*M+j+1)/2].push_back(((ni-1)*M+nj+1)/2);
                }
            }

        l2.clear();
        l2.resize(s+1, -1);

        r2.clear();
        r2.resize(s+1, -1);

        for(int i=1; i<=s; i++) {
            vis.clear();
            vis.resize(s+1);

            g(i);
        }

        vector<vector<char>> w(v);

        for(int ii=1; ii<=N; ii++)
            for(int jj=1; jj<=M; jj++) {
                if(v[ii][jj] != '.') continue;

                int x = ((ii-1)*M+jj+1)/2;

                bool check = false;

                if((ii + jj) % 2 == 1 && r1[x] == -1) check = true;
                if((ii + jj) % 2 == 0 && r2[x] == -1) check = true;

                if(check) {
                    w[ii][jj] = 'B';
                    continue;
                }

                if((ii + jj) % 2 == 1) {
                    tadj.clear(); tadj = adj1;

                    for(int k=0; k<4; k++) {
                        int ni = ii + di[k];
                        int nj = jj + dj[k];

                        if(ni < 1 || nj < 1 || ni > N || nj > M) continue;
                        if(v[ni][nj] != '.') continue;

                        int y = ((ni-1)*M+nj+1)/2;

                        if(count(tadj[y].begin(), tadj[y].end(), x) > 0)
                            tadj[y].erase(remove(tadj[y].begin(), tadj[y].end(), x), tadj[y].end());
                    }

                    ll.clear(); ll = l1;
                    rr.clear(); rr = r1;

                    int z = rr[x];

                    ll[rr[x]] = -1;
                    rr[x] = -1;

                    vis.clear(); vis.resize(s+1);

                    if(h(z)) w[ii][jj] = 'B';
                    else w[ii][jj] = 'A';
                }
                if((ii + jj) % 2 == 0) {
                    tadj.clear(); tadj = adj2;

                    for(int k=0; k<4; k++) {
                        int ni = ii + di[k];
                        int nj = jj + dj[k];

                        if(ni < 1 || nj < 1 || ni > N || nj > M) continue;
                        if(v[ni][nj] != '.') continue;

                        int y = ((ni-1)*M+nj+1)/2;

                        if(count(tadj[y].begin(), tadj[y].end(), x) > 0)
                            tadj[y].erase(remove(tadj[y].begin(), tadj[y].end(), x), tadj[y].end());
                    }

                    ll.clear(); ll = l2;
                    rr.clear(); rr = r2;

                    vis.clear(); vis.resize(s+1);

                    int z = rr[x];

                    ll[rr[x]] = -1;
                    rr[x] = -1;

                    if(h(z)) w[ii][jj] = 'B';
                    else w[ii][jj] = 'A';
                }
            }

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) cout << w[i][j];
            cout << "\n";
        }
        cout << "\n";
    }
}

 

 

백준 BOJ 2051번 : 최소 버텍스 커버

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

이분 그래프가 주어질 때 최소 정점 커버에 해당하는 정점들의 목록을 구하는 문제이다.

중요한 문제이므로 위에다가 배치한다.

 

 

백준 BOJ 10058번 : 센서 네트워크 풀이 (난이도 Ruby V / 루비 5)

 

위 포스트의 중간에 정리된 정리를 사용하면 된다. (최소 정점 커버 = (L - X) ∪ (R ∩ X))

최소 정점 커버에 대한 엄밀한 증명은 kks227님의 블로그에 정리되어있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N+1);

    for(int i=1; i<=N; i++) {
        int K; cin >> K;

        while(K--) {
            int x; cin >> x;

            adj[i].push_back(x);
        }
    }

    l.resize(N+1, -1);
    r.resize(M+1, -1);

    int match = 0;

    for(int i=1; i<=N; i++) {
        vis.clear();
        vis.resize(N+1);

        f(i);
    }

    vector<bool> lvis(N+1), rvis(M+1);

    for(int i=1; i<=N; i++) {
        if(l[i] != -1 || lvis[i]) continue;

        lvis[i] = true;

        queue<pair<bool, int>> q;
        q.push({true, i});

        while(!q.empty()) {
            bool isLeft = q.front().first;
            int x = q.front().second;
            q.pop();

            if(isLeft) {
                for(int j=0; j<adj[x].size(); j++) {
                    int y = adj[x][j];

                    if(l[x] != y && !rvis[y]) {
                        rvis[y] = true;
                        q.push({false, y});
                    }
                }
            }
            else {
                for(int j=1; j<=N; j++) {
                    int y = j;

                    if(lvis[y]) continue;
                    if(count(adj[y].begin(), adj[y].end(), x) == 0) continue;

                    for(int k=0; k<adj[y].size(); k++) {
                        if(adj[y][k] != x) continue;

                        if(r[x] == y) {
                            lvis[y] = true;
                            q.push({true, y});
                        }
                    }
                }
            }
        }
    }

    vector<int> v, u;

    for(int i=1; i<=N; i++)
        if(!lvis[i]) v.push_back(i);

    for(int i=1; i<=M; i++)
        if(rvis[i]) u.push_back(i);

    cout << v.size() + u.size() << "\n";

    cout << v.size() << " ";

    for(int i=0; i<v.size(); i++) cout << v[i] << " ";
    cout << "\n";

    cout << u.size() << " ";

    for(int i=0; i<u.size(); i++) cout << u[i] << " ";
    cout << "\n";
}

 

 

백준 BOJ 13980번 : Maximum Islands

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

N x M 크기의 배열이 주어지고, L은 땅, W은 물, C는 구름으로 가려져서 어떤 것인지 보이지 않는다고 했을 때, 상하좌우가 물로 분리된 땅 덩어리를 섬이라고 한다면 가능한 섬의 최댓값을 구하는 문제이다.

 

최대 정점 커버를 활용하여 이분 매칭으로 풀이할 수 있다.

L은 이미 땅이니 인접한 부분 중 C가 모두 물이라고 생각해도 가능한 최대 섬의 수에 영향을 주지 않는다.

따라서 인접한 부분에 L이 없는 C들을 가지고 이분 매칭을 수행하여 최대 매칭 수를 그러한 C들의 수에서 빼주면, 추가로 형성할 수 있는 최대 섬의 수가 된다. (최대 정점 커버 = 정점 수 - 최대 매칭 수라는 정리를 사용한 것이다.)

따라서 기존의 L은 DFS 등으로 탐색하여 섬의 수를 세어주고, 나머지는 이분 매칭으로 풀이해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int N, M;
vector<vector<char>> v;
vector<vector<bool>> lvis;

void g(int x, int y) {
    lvis[x][y] = true;

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
        if(v[nx][ny] != 'L' || lvis[nx][ny]) continue;

        g(nx, ny);
    }
}

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;

    v.resize(N+1, vector<char>(M+1));

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) cin >> v[i][j];

    lvis.resize(N+1, vector<bool>(M+1));
    int lnd = 0;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            if(v[i][j] == 'L' && !lvis[i][j]) {
                g(i, j);
                lnd++;
            }

    vector<vector<bool>> u(N+1, vector<bool>(M+1));
    int cnt = 0;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            if(v[i][j] != 'C') continue;

            int di[4] = {1, -1, 0, 0};
            int dj[4] = {0, 0, 1, -1};

            bool check = true;

            for(int k=0; k<4; k++) {
                int ni = i + di[k];
                int nj = j + dj[k];

                if(ni < 1 || nj < 1 || ni > N || nj > M) continue;
                if(v[ni][nj] == 'L') check = false;
            }

            if(check) {
                u[i][j] = true;
                cnt++;
            }
        }

    int s = (N*M + 1) / 2;

    adj.resize(s+1);

    for(int i=1; i<=N; i++)
        for(int j=!(i%2)+1; j<=M; j+=2) {
            if(!u[i][j]) continue;

            int di[4] = {1, -1, 0, 0};
            int dj[4] = {0, 0, 1, -1};

            for(int k=0; k<4; k++) {
                int ni = i + di[k];
                int nj = j + dj[k];

                if(ni < 1 || nj < 1 || ni > N || nj > M) continue;
                if(v[ni][nj] != 'C' || !u[ni][nj]) continue;

                adj[((i-1)*M+j+1)/2].push_back(((ni-1)*M+nj+1)/2);
            }
        }

    l.resize(s+1, -1);
    r.resize(s+1, -1);

    int match = 0;

    for(int i=1; i<=s; i++) {
        vis.clear();
        vis.resize(s+1);

        if(f(i)) match++;
    }

    int ans = lnd + cnt - match;

    cout << ans << "\n";
}

 

 

백준 BOJ 12428번 : 박테리아 (Large)

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

** 이 문제의 풀이 코드로 백준 BOJ 12427번 : 박테리아 (Small) 문제를 정답 처리 받을 수 있다.

 

N x M x K 크기의 배열이 주어질 때, K개의 각 층에서 상하좌우로 인접한 .은 하나의 방이고, 상하 모두 방인 칸끼리는 박테리아를 보관할 수 없다고 할 때, 최대 몇 개의 방에 박테리아를 보관할 수 있는지 구하는 문제이다.

 

먼저 DFS 또는 BFS로 각 층에 있는 방들에 번호를 매기고, 각 층에 대해 각 방 칸의 위 아래 칸에 방이 인접해있는지를 검사하여 해당 방의 번호들끼리 간선을 연결한다.

이 때 이분 그래프가 형성되어야 이분 매칭을 수행할 수 있으므로, 홀수번째 층과 짝수번째 층을 나누어 매칭해준다. (2층 이상 떨어진 칸은 절대로 인접할 수 없으므로 이분 그래프가 만들어진다.)

그 다음 이분 매칭을 수행해준 뒤 방의 수에서 매칭의 수를 빼주면 답이 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N, M, K; cin >> N >> M >> K;

        vector<vector<vector<int>>> v(K+1, vector<vector<int>>(N+1, vector<int>(M+1, -1)));

        for(int i=1; i<=K; i++)
            for(int j=1; j<=N; j++)
                for(int k=1; k<=M; k++) {
                    char ch; cin >> ch;

                    if(ch == '.') v[i][j][k] = 0;
                }

        int cnt = 0;

        for(int i=1; i<=K; i++)
            for(int j=1; j<=N; j++)
                for(int k=1; k<=M; k++) {
                    if(v[i][j][k] != 0) continue;

                    cnt++;
                    v[i][j][k] = cnt;

                    queue<pair<int, int>> q;
                    q.push({j, k});

                    vector<vector<bool>> vis(N+1, vector<bool>(M+1));
                    vis[j][k] = true;

                    while(!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();

                        int dx[4] = {1, -1, 0, 0};
                        int dy[4] = {0, 0, 1, -1};

                        for(int l=0; l<4; l++) {
                            int nx = x + dx[l];
                            int ny = y + dy[l];

                            if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
                            if(v[i][nx][ny] != 0) continue;

                            v[i][nx][ny] = cnt;
                            q.push({nx, ny});
                        }
                    }
                }

        adj.clear();
        adj.resize(cnt+1);

        for(int i=1; i<=K; i+=2)
            for(int j=1; j<=N; j++)
                for(int k=1; k<=M; k++) {
                    if(v[i][j][k] == -1) continue;

                    int dz[2] = {1, -1};

                    for(int l=0; l<2; l++) {
                        int nz = i + dz[l];

                        if(nz < 1 || nz > K) continue;
                        if(v[nz][j][k] == -1) continue;

                        adj[v[i][j][k]].push_back(v[nz][j][k]);
                    }
                }

        l.clear(); l.resize(cnt+1, -1);
        r.clear(); r.resize(cnt+1, -1);

        int match = 0;

        for(int i=1; i<=cnt; i++) {
            vis.clear();
            vis.resize(cnt+1);

            if(f(i)) match++;
        }

        int ans = cnt - match;

        cout << "Case #" << t << ": " << ans << "\n";
    }
}

 

 

백준 BOJ 12634번 : Stock Charts (Large)

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

** 이 문제의 풀이 코드로 백준 BOJ 12988번 : 주식 차트, 백준 BOJ 12633번 : Stock Charts (Small) 문제를 정답 처리 받을 수 있다.

(12988번은 테스트케이스 부분을 조금만 수정해주면 된다.)

 

N개의 주식 차트가 주어지는데, 서로 차트가 겹치는 것은 같은 차트에 넣을 수 없다고 한다면 차트가 최소 몇 개 필요한지 구하는 문제이다.

 

역시 최대 매칭을 구한 뒤 매칭 수만큼 빼주면 되는 것으로 보이는 문제이다.

당연히 일반 그래프에서의 최대 매칭은 구현하기 매우 어려우므로, 주어진 상황을 이분 그래프로 만드는 것이 핵심이다.

해결책은 그래프의 상하 관계대로만 간선을 연결하는 것이다.

예를 들어 2번 그래프가 3번 그래프보다 위에 있다면, 2번 노드에서 3번 노드로 간선을 연결하는 것이다. (3번 노드에서 2번 노드로 연결하는 것이 아니라)

이러한 방식으로 간선들을 연결해준다면, 최대 매칭을 구했을 때 얻어지는 매칭 수만큼 차트의 개수를 줄일 수 있고 반례가 존재하지 않게 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N, M; cin >> N >> M;

        vector<vector<int>> v(N, vector<int>(M));

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++) cin >> v[i][j];

        adj.clear();
        adj.resize(N);

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) {
                if(i == j) continue;

                bool check = true;

                for(int k=0; k<M; k++)
                    if(v[i][k] >= v[j][k]) check = false;

                if(check) adj[i].push_back(j);
            }

        l.clear(); l.resize(N, -1);
        r.clear(); r.resize(N, -1);

        int match = 0;

        for(int i=0; i<N; i++) {
            vis.clear();
            vis.resize(N);

            if(f(i)) match++;
        }

        int ans = N - match;

        cout << "Case #" << t << ": " << ans << "\n";
    }
}

 

 

백준 BOJ 15007번 : Easter Eggs

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

2차원 좌표 평면 상에 N개의 파란 점과 M개의 빨간 점이 주어지고, 이들 중 K개의 점을 선택하여 빨간 점과 파란 점의 최소 거리가 최대가 되도록 했을 때 그 거리를 구하는 문제이다.

 

거리 임계 값에 대해 이분 탐색을 수행하면서, 현재 임계 거리 값 이하가 되는 것들에 대해 간선을 연결하여 (파란 점 → 빨간 점 방향으로 연결한다.) 이분 매칭을 수행해준 뒤 최대 정점 독립 집합이 K 이상이면 답의 최댓값을 갱신해주는 방식으로 답을 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(x == y) continue;

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N; cin >> N;

        adj.clear();
        adj.resize(N+1);

        map<string, int> m1, m2;

        int x = 0, y = 0;

        for(int i=1; i<=N; i++) {
            string a, b; cin >> a >> b;

            if(m1[a] == 0) m1[a] = ++x;
            if(m2[b] == 0) m2[b] = ++y;
            
            
        }

        l.clear(); l.resize(N+1, -1);
        r.clear(); r.resize(N+1, -1);

        int ans = 0;

        for(int i=1; i<=N; i++) {
            vis.clear();
            vis.resize(N+1);

            if(f(i)) ans++;
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 17994번 : Swap Free

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

N개의 애너그램 관계인 단어들이 주어질 때, 이들 중 몇 개를 선택하여 만든 집합들 중 어떤 두 단어를 골라도 두 철자를 한 번만 swap하여 만들 수 있는 단어 관계가 없도록 하는 최대 집합 크기를 구하는 문제이다.

 

단어 A에서 B를 만들 때 최소 x번 swap하여야 하고, B에서 C를 만들 때 최소 y번 swap해야 하고, A에서 C를 만들 때 z번 swap해야 한다면 x + y와 z의 홀짝성이 동일하다.

따라서 첫 번째 단어에서 홀수 횟수만큼 swap해야 만들 수 있는 단어들은 오른쪽에, 짝수 횟수만큼 swap해야 만들 수 있는 단어들은 왼쪽에 (첫 번째 단어 포함, 0번이니까) 위치시킨 뒤 이분 매칭을 통해 최대 정점 독립 집합의 크기를 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(x == y) continue;

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N; cin >> N;

        adj.clear();
        adj.resize(N+1);

        map<string, int> m1, m2;

        int x = 0, y = 0;

        for(int i=1; i<=N; i++) {
            string a, b; cin >> a >> b;

            if(m1[a] == 0) m1[a] = ++x;
            if(m2[b] == 0) m2[b] = ++y;
            
            
        }

        l.clear(); l.resize(N+1, -1);
        r.clear(); r.resize(N+1, -1);

        int ans = 0;

        for(int i=1; i<=N; i++) {
            vis.clear();
            vis.resize(N+1);

            if(f(i)) ans++;
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 7064번 : Air Raid

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

루프 없는 단방향 그래프가 주어질 때, 서로 경로가 겹치지 않고 모든 노드를 방문할 수 있는 최소 사람 수를 구하는 문제이다.

 

양쪽에 각각 N개의 노드를 두고 간선 방향대로 간선을 연결한 뒤, 최대 매칭을 찾아주면 매칭 수만큼 필요한 사람 수가 줄어들게 되므로 N - (최대 매칭 수)가 답이 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        adj.clear();
        adj.resize(N+1);

        while(M--) {
            int x, y; cin >> x >> y;

            adj[x].push_back(y);
        }

        l.clear(); l.resize(N+1, -1);
        r.clear(); r.resize(N+1, -1);

        int match = 0;

        for(int i=1; i<=N; i++) {
            vis.clear();
            vis.resize(N+1);

            if(f(i)) match++;
        }

        int ans = N - match;

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 19647번 : Unique Solution

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

이분 그래프에서 N개 모두 매칭이 가능한 경우가 유일한지를 검사하는 문제이다.

 

이분 매칭 함수를 두 개 구현하여 하나는 앞에서부터 탐색하고 하나는 뒤에서부터 탐색하여 두 해가 동일한지 확인해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj;
vector<int> l1, r1, l2, r2;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r1[y] == -1 || (!vis[r1[y]] && f(r1[y]))) {
            l1[x] = y, r1[y] = x;

            return true;
        }
    }

    return false;
}

bool g(int x) {
    vis[x] = true;

    for(int i=adj[x].size()-1; i>=0; i--) {
        int y = adj[x][i];

        if(r2[y] == -1 || (!vis[r2[y]] && g(r2[y]))) {
            l2[x] = y, r2[y] = x;

            return true;
        }
    }

    return false;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    adj.resize(N+1);

    for(int i=1; i<=N; i++) {
        int M; cin >> M;

        while(M--) {
            int x; cin >> x;

            adj[i].push_back(x);
        }
    }

    l1.resize(N+1, -1);
    r1.resize(N+1, -1);

    for(int i=1; i<=N; i++) {
        vis.clear();
        vis.resize(N+1);

        f(i);
    }

    l2.resize(N+1, -1);
    r2.resize(N+1, -1);

    for(int i=1; i<=N; i++) {
        vis.clear();
        vis.resize(N+1);

        g(i);
    }

    if(l1 != l2) {
        cout << -1 << "\n";
        return 0;
    }

    cout << 1 << "\n";

    for(int i=1; i<=N; i++) cout << l1[i] << " ";
    cout << "\n";
}