이분 매칭 최대 독립 집합 (Maximum Independent Set) 외 문제 풀이

이 포스트에서는 이분 매칭의 응용 중 하나인 최대 독립 집합(Maximum Independent Set)에 대해서 다룬다.

어떤 노드들의 집합에서 어떤 두 노드도 서로 간선으로 연결되어 있지 않을 때, 이 집합을 독립 집합이라고 한다.

그래프에서 최대 크기의 독립 집합을 최대 독립 집합이라고 한다.

 

이분 매칭 문제에서 최대 독립 집합은 전체 노드에서 최소 정점 커버(= 최소 꼭짓점 덮개)를 뺀 나머지가 된다.

그리고 최소 정점 커버는 쾨니그의 정리에 의해서 최대 매칭 수와 동일하다.

 

즉, 최대 독립 집합의 크기 I = V - M이다. (V = vertex의 수, M = 최대 매칭 수)

 

 

백준 BOJ 14986번 : Punching Power

문제 난이도 : Platinum III (난이도 기여로 난이도 상향시킴)

알고리즘 분류 : 이분 매칭

 

기계를 설치할 수 있는 좌표들의 후보가 N개 주어지고, 거리가 1.3 이하인 두 지점에 모두 기계를 설치하는 것은 불가능하다고 할 때, 최대로 설치할 수 있는 기계의 수를 구하는 문제이다.

 

거리가 1.3 이하라면 결국은 인접한 칸 사이에만 설치되지 않도록 기계들을 배치하면 된다.

인접한 노드들을 간선으로 연결한 뒤 여기에서 최대 독립 집합을 구해주면 된다.

다만 이를 위해서는 위에서 사용한 I = V - M의 식을 사용하기 위해 최대 매칭을 구해야 하므로 이분 그래프로 바꾸어줄 필요가 있다.

따라서 (x + y) % 2 = 0인 칸과 (x + y) % 2 = 1인 칸 두 가지로 나눈다. (체스판의 검은 칸, 흰 칸과 같다.)

간선들로 연결해서 최대 매칭을 구해주고, 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 N;

    while(cin >> N) {
        vector<pair<int, int>> v, u;
        map<pair<int, int>, int> vm, um;
        int vcnt = 0, ucnt = 0;

        for(int i=0; i<N; i++) {
            int x, y; cin >> x >> y;

            if((x + y) % 2 == 0) {
                v.push_back({x, y});
                vm[{x, y}] = ++vcnt;
            }
            else {
                u.push_back({x, y});
                um[{x, y}] = ++ucnt;
            }
        }

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

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

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

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

                if(um[{nx, ny}] != 0) adj[vm[{x, y}]].push_back(um[{nx, ny}]);
            }
        }

        l.clear();
        l.resize(vcnt+1, -1);

        r.clear();
        r.resize(ucnt+1, -1);

        int match = 0;

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

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

        int ans = N - match;

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

 

 

백준 BOJ 16726번 : 영과일 학회방

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N x M 크기의 배열이 주어질 때, 1 x 1 또는 1 x 2 블럭으로 맵의 빈칸을 채운다고 한다면 최소로 필요한 블럭의 수를 구하는 문제이다.

 

이분 매칭 개수의 여집합을 이용하는 대표적인 문제이다.

맵을 체스판처럼 생각하여, 검은색 칸에 해당하는 노드와 흰색 칸에 해당하는 노드들로 나누어 서로 붙어있는 빈칸 사이인 노드들을 간선으로 연결해준 뒤 이분 매칭을 수행한다.

최대 매칭 값은 최대로 놓을 수 있는 1 x 2 블럭의 수와 동일하므로, 전체 빈칸 수 - 1 x 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 N, M; cin >> N >> M;

    vector<vector<char>> v(N+1, vector<char>(M+1));
    int cnt = 0;

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

            if(v[i][j] == '.') cnt++;
        }

    adj.resize(N*M + 1);

    for(int i=1; i<=N; i++)
        for(int j=!(i%2)+1; j<=M; j+=2) {
            if(v[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] != '.') continue;

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

    int s = (N*M + 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 = cnt - match;

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

 

 

백준 BOJ 7058번 : Royal guards

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N x M 배열이 주어지고, 0으로 된 칸은 경비병을 배치할 수 있는 칸, 1은 빈 칸이나 경비병을 배치할 수 없는 칸, 2는 벽이라고 할 때, 벽으로 막혀있지 않고 같은 행이나 열인 병사끼리는 서로 공격한다고 할 때, 서로 공격하지 않도록 경비병을 배치하는 최대 수를 구하는 문제이다.

 

각 0으로 된 빈칸에 행과 열 번호를 부여하고, 행 번호와 열 번호 사이의 이분 그래프를 만들어준 뒤 최대 매칭을 찾아주면 된다.

 

이 문제를 상단에 배치한 이유는 바로 매칭을 구해야하기 때문인데, 이것은 각 {i, l[i]} 값들에 해당하는 행 번호와 열 번호를 가지고 있는 칸을 반복문으로 찾아주면 된다.

 

 

#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;

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

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

    vector<vector<int>> u(N+1, vector<int>(M+1));
    int rcnt = 1;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            if(v[i][j] == 0) u[i][j] = rcnt;
            if(v[i][j] != 2 && (j == M || v[i][j+1] == 2)) rcnt++;
        }

    rcnt--;

    vector<vector<int>> w(N+1, vector<int>(M+1));
    int ccnt = 1;

    for(int i=1; i<=M; i++)
        for(int j=1; j<=N; j++) {
            if(v[j][i] == 0) w[j][i] = ccnt;
            if(v[j][i] != 2 && (j == N || v[j+1][i] == 2)) ccnt++;
        }

    ccnt--;

    adj.resize(rcnt+1);

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            if(v[i][j] == 0) adj[u[i][j]].push_back(w[i][j]);


    l.resize(rcnt+1, -1);
    r.resize(ccnt+1, -1);

    int ans = 0;

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

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

    cout << ans << "\n";

    vector<pair<int, int>> vv;

    for(int i=1; i<=rcnt; i++)
                if(i == r[l[i]]) vv.push_back({i, l[i]});

    for(int i=0; i<vv.size(); i++)
        for(int j=1; j<=N; j++)
            for(int k=1; k<=M; k++)
                if(u[j][k] == vv[i].first && w[j][k] == vv[i].second) cout << j << " " << k << "\n";
}

 

 

백준 BOJ 2787번 : 흔한 수열 문제

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N 이하의 자연수로 이루어진 길이 N인 순열이 있고, M개의 힌트가 주어질 때 순열을 맞추는 문제이다.

이 때 힌트란 2가지로 분류되는데, 1 a b c의 경우 a번째부터 b번째 수 중 최댓값이 c라는 것이고, 2 a b c의 경우 최솟값이 c라는 것이다.

 

다음의 두 가지 조건을 사용하면 된다. 1번 쿼리를 예시로 들겠다.

1. 각 인덱스에 해당하는 최솟값을 1, 최댓값을 N으로 두고 구간을 좁힐 수 있다. 1 a b c이면 a번 원소부터 b번 원소들 중 최댓값을 기존의 최댓값과 c 중 더 작은 값으로 갱신할 수 있다.

2. 각 숫자가 나타나는 인덱스 범위의 최솟값을 1, 최댓값을 N으로 두고 구간을 좁힐 수 있다. a b c 쿼리에 대해, c라는 숫자는 기존의 최솟값과 a 중 더 큰 인덱스로 갱신이 가능하며, 반대로 인덱스의 최댓값과 b 중 더 작은 인덱스로 갱신이 가능하다.

 

이제 1, 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 N, M; cin >> N >> M;

    vector<int> minv(N+1, 1), maxv(N+1, N);
    vector<int> minr(N+1, 1), maxr(N+1, N);

    while(M--) {
        int Q, a, b, c; cin >> Q >> a >> b >> c;

        if(Q == 1) {
            for(int i=a; i<=b; i++) maxv[i] = min(maxv[i], c);
        }
        else if(Q == 2) {
            for(int i=a; i<=b; i++) minv[i] = max(minv[i], c);
        }

        minr[c] = max(minr[c], a);
        maxr[c] = min(maxr[c], b);
    }

    adj.resize(N+1);

    for(int i=1; i<=N; i++)
        for(int j=minv[i]; j<=maxv[i]; j++)
            if(minr[j] <= i && i <= maxr[j]) adj[i].push_back(j);

    l.resize(N+1, -1);
    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++;
    }

    if(match < N) {
        cout << -1 << "\n";
        return 0;
    }

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

 

 

백준 BOJ 22620번 : Defend the Bases

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭, 이분 탐색

 

N개의 군대의 좌표와 이동 속도, M개의 기지의 좌표가 주어질 때 모든 기지에 하나 이상의 군대를 배치하기 위해 필요한 최소 시간을 구하는 문제이다.

 

만약 제한 시간이 주어지고 최대로 하나 이상의 군대를 배치할 수 있는 기지의 수를 구하는 문제라면 이분 매칭으로 쉽게 구할 수 있다.

따라서 이 상황을 확장시켜 이분 탐색으로 미리 제한 시간을 가정하고, 그에 따른 match 값이 M인 경우 제한 시간을 줄여나가는 식으로 풀이할 수 있다.

 

 

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

struct s { double x, y, v; };

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);

    cout << fixed;
    cout.precision(8);

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

        vector<s> v(N), u(M);

        for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y >> v[i].v;
        for(int i=0; i<M; i++) cin >> u[i].x >> u[i].y;

        double ll = 0, rr = INT_MAX, ans = INT_MAX, tr = 1e2;

        while(tr--) {
            double m = (ll + rr) / 2;

            adj.clear();
            adj.resize(M);

            for(int i=0; i<N; i++)
                for(int j=0; j<M; j++)
                    if(sqrt(pow(v[i].x - u[j].x, 2) + pow(v[i].y - u[j].y, 2)) / v[i].v <= m) adj[j].push_back(i);

            l.clear();
            l.resize(M, -1);

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

            int match = 0;

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

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

            if(match == M) {
                ans = min(ans, m);
                rr = m;
            }
            else ll = m;
        }

        cout << ll << "\n";
    }
}

 

 

백준 BOJ 13470번 : Programming Tutors

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭, 이분 탐색

 

N명의 학생의 좌표와 N명의 교사의 좌표가 2차원 상에서 주어질 때, 하나의 교사가 서로 다른 하나의 학생으로 이동할 때 가장 맨해튼 거리가 먼 거리가 최소가 되도록 매치했을 때 그 최솟값을 구하는 문제이다.

 

위의 문제와 비슷한 방법으로, 이분 매칭을 하되 제한 값을 미리 정해두고 그 거리 이하인 노드들 내에서만 간선을 연결한 뒤 수행해준 뒤 매치된 쌍의 수가 N개이면 제한 거리를 줄여보고, 그렇지 않으면 제한 거리를 늘리는 식으로 조절해가면서 최소 제한 거리를 구해주면 된다.

 

 

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

struct s { int x, y; };

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; cin >> N;

    vector<s> v(N), u(N);

    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;
    for(int i=0; i<N; i++) cin >> u[i].x >> u[i].y;

    int ll = 0, rr = INT_MAX, ans = INT_MAX;

    while(ll <= rr) {
        int m = (ll + rr) / 2;

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

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                if(abs(v[i].x - u[j].x) + abs(v[i].y - u[j].y) <= m) 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++;
        }

        if(match == N) {
            ans = min(ans, m);
            rr = m - 1;
        }
        else ll = m + 1;
    }

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

 

 

백준 BOJ 9577번 : 토렌트

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

 

N개의 토렌트 조각이 있고 M명의 회원들이 접속한 시각에 해당 회원이 가지고 있는 조각 하나를 1초에 받을 수 있다고 할 때, 모든 조각을 모으기 위한 최소 시간을 구하는 문제이다.

 

이분 매칭으로 푸는 것을 알았다면, 어떤 그룹과 어떤 그룹 사이의 매칭을 수행할지 고민해보면 된다.

각 시간 (초 단위) → 토렌트 조각 관계로 연결을 해준 뒤 이분 매칭 알고리즘을 돌려주면 된다.

 

 

#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(101);

        while(M--) {
            int a, b, K; cin >> a >> b >> K;

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

                for(int i=a; i<b; i++) adj[i].push_back(x);
            }
        }

        l.clear();
        l.resize(101, -1);

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

        int match = 0;
        bool check = false;

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

            if(f(i)) match++;

            if(match == N) {
                cout << i+1 << "\n";

                check = true;
                break;
            }
        }

        if(!check) cout << -1 << "\n";
    }
}

 

 

백준 BOJ 25846번 : Make the Team

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

 

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 N; cin >> N;

    adj.resize(1001);

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

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

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

    l.clear();
    l.resize(1001, -1);

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

    int match = 0;

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

        if(f(i)) match++;

        if(match == N) {
            cout << i+1 << "\n";
            break;
        }
    }
}

 

 

백준 BOJ 3736번 : System Engineer

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

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 N;

    while(cin >> N) {
        adj.clear();
        adj.resize(N);

        for(int i=0; i<N; i++) {
            int a, M; char ch;
            cin >> a >> ch >> ch >> M >> ch;

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

                adj[a].push_back(b - N);
            }
        }

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

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

        int ans = 0;

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

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

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

 

 

백준 BOJ 5780번 : Uncle Tom's Inherited Land

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N x M 크기의 배열이 있고 그들 중 연못에 해당하는 칸들의 목록이 주어질 때, 연못이 아닌 땅은 1 x 2 크기로 하나씩 판매할 수 있다고 할 때, 판매 가능한 땅의 최대 개수를 구하는 문제이다.

 

위에서 풀이한 백준 BOJ 16726번 : 영과일 학회방 문제의 풀이와 비슷하게 풀이하면 된다.

체스판의 검은칸, 흰칸을 나누어 이분 매칭시켜준 뒤 두 칸이 모두 육지인 칸 사이를 간선으로 연결하고, 이분 매칭을 시켜 최대 매칭 수를 구해주면 된다.

 

 

#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);

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

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

        int K; cin >> K;

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

            v[x][y] = false;
        }

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

        for(int i=1; i<=N; i++)
            for(int j=!(i%2)+1; j<=M; j+=2) {
                if(!v[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]) continue;

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

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

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

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

        int ans = 0;

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

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

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

 

 

백준 BOJ 5924번 : Cow Steeplechase

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N개의 선분이 가로선 또는 세로선으로 주어질 때, 이들 중 서로 겹치지 않는 것들을 최대한 뽑았을 때 그 개수를 구하는 문제이다.

단, 평행한 두 선분이 겹치는 경우는 존재하지 않는다고 가정한다.

 

가로 선분과 세로 선분을 서로 각각의 그룹으로 분류한 뒤 서로 교차하는 것끼리 간선으로 연결해주면 이분 그래프가 만들어지며, 여기에 이분 매칭을 사용하여 최대 매칭 수를 N에서 빼주면 답이 된다.

 

아래의 가정 때문에 문제를 훨씬 간단하게 풀이할 수 있다.

만약 평행한 선분이 겹치지 않는다는 조건이 없었다면, 선분 교차 판정 알고리즘까지 가지고 와서 사용해야한다.

(그랬다면 난이도가 Platinum I 이상으로 올라갔을 것 같다.)

 

 

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

struct s { int x1, y1, x2, y2; };

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; cin >> N;

    vector<s> v, u;

    for(int i=0; i<N; i++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

        if(y1 == y2) {
            if(x1 > x2) swap(x1, x2);
            v.push_back({x1, y1, x2, y2});
        }
        else {
            if(y1 > y2) swap(y1, y2);
            u.push_back({x1, y1, x2, y2});
        }
    }

    adj.resize(v.size());

    for(int i=0; i<v.size(); i++)
        for(int j=0; j<u.size(); j++)
            if(v[i].x1 <= u[j].x1 && u[j].x1 <= v[i].x2
               && u[j].y1 <= v[i].y1 && v[i].y1 <= u[j].y2) adj[i].push_back(j);

    l.resize(v.size(), -1);
    r.resize(u.size(), -1);

    int match = 0;

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

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

    int ans = N - match;

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

 

 

백준 BOJ 10371번 : Irrigation Lines

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N x M 배열에 0 또는 1의 값이 주어질 때, 행 또는 열 몇 개를 선택하여 1이 전부 선택되도록 하는 최소 선택 수를 구하는 문제이다.

 

1의 값을 가지는 위치의 행과 열을 간선으로 이어 이분 그래프를 만들면, 쾨니그의 정리에 의해 최소 꼭짓점 덮개 수 = 최대 매칭 수이므로 이분 매칭으로 풀이할 수 있다.

 

 

#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;

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

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

                if(c == '1') adj[i].push_back(j);
            }

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

        r.clear();
        r.resize(M+1, -1);

        int ans = 0;

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

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

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

 

 

백준 BOJ 10532번 : Book Club

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

N명의 사람들이 있고 M개의 순서쌍 (a, b)에 대해 a번 사람이 b번 사람의 책을 좋아한다고 하자.

모든 사람이 책을 하나씩 전달받고 전달하여 순환이 가능한지 여부를 구하는 문제이다.

 

왼쪽에 N개의 노드, 오른쪽에 N개의 노드를 설정한 뒤 문제에서 제시한대로 M개의 간선을 연결하여 이분 그래프를 만들고 이분 매칭을 수행하여 최대 매치 수가 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 N, M; cin >> N >> M;

        adj.resize(N);

        while(M--) {
            int a, b; cin >> a >> b;

            adj[a].push_back(b);
        }

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

        int match = 0;

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

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

        if(match == N) cout << "YES\n";
        else cout << "NO\n";
}

 

 

백준 BOJ 10850번 : Bounty Hunter

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

 

노드가 N개인 단방향 그래프가 주어질 때, 한 사람이 하나의 경로로 지나간 노드들을 체크하되 한 사람이 지나간 노드는 다른 사람이 지나갈 수 없다고 할 때, 모든 노드들을 체크하기 위해 필요한 최소 인원 수를 구하는 문제이다.

 

위 문제와 똑같이 왼쪽에 N개 노드, 오른쪽에도 N개 노드를 구성한 뒤 a → b간선의 방향대로 왼쪽 a번 노드를 오른쪽 b번 노드로 연결한다.

이렇게 만들어진 이분 그래프에 대해 이분 매칭을 수행하여 최대 매칭을 찾는다.

이분 매칭을 통해 선택된 하나의 간선은 한 사람의 한 번의 이동으로 고려할 수 있고, 간선이 두 개 이상의 노드를 공유하지 않으므로 이들은 경로가 겹치지 않는 최대 이동에 해당한다.

따라서 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 N; cin >> N;

        adj.resize(N);

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

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

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

        l.resize(N, -1);
        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 << ans << "\n";
}

 

 

백준 BOJ 17238번 : Delicious Pineapple Pizza

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭, 이분 탐색

 

길이 N인 수열 A와 B가 주어질 때, N개의 쌍을 만들어 a ^ b 값의 최솟값이 최대가 되도록 매칭하고, 그 때의 최솟값을 구하는 문제이다.

 

이분 매칭으로 값들을 매칭시켜야 하는 것은 쉽게 생각할 수 있다.

이분 탐색을 이용하여 특정 임계값 이상의 연산 값을 가지는 경우만 간선으로 연결하여 이분 매칭을 수행하고, 최대 매칭 값이 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 N; cin >> N;

    vector<int> v(N), u(N);
    for(int i=0; i<N; i++) cin >> v[i];
    for(int i=0; i<N; i++) cin >> u[i];

    int ll = 0, rr = INT_MAX, ans = 0;

    while(ll <= rr) {
        int m = (ll + rr) / 2;

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

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                if((v[i] ^ u[j]) >= m) 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++;
        }

        if(match == N) {
            ans = max(ans, m);
            ll = m + 1;
        }
        else rr = m - 1;
    }

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

 

 

백준 BOJ 13503번 : 최소 체인 커버

문제 난이도 : Platinum II

알고리즘 분류 : 이분 매칭

 

단방향 그래프가 주어질 때, 서로 겹치지 않는 몇 개의 경로로 모든 정점을 지나가려고 할 때 필요한 최소 경로의 수를 구하는 문제이다.

 

이분 매칭으로 최대 매칭 수를 구한 뒤, 정점의 수에서 매칭 수를 빼주면 곧 경로의 수가 된다.

 

 

#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);

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

        adj[x].push_back(y);
    }

    l.resize(N+1, -1);
    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";
}