이분 매칭 (Bipartite Matching) 문제 풀이 모음 221019

restudy 2022. 10. 19. 04:00

이분 매칭 알고리즘에 대해서는 이전에 다룬 적도 있고 문제 풀이도 한 적 있지만 잊어버린 내용이 많아서 공부를 위해 다시 정리해본다.

이분 매칭 알고리즘

1. 이분 그래프란 그래프의 정점을 같은 그룹의 노드 사이에 간선으로 연결된 노드 쌍이 존재하지 않도록 두 그룹으로 나눌 수 있는 그래프를 의미한다.

2. 이분 매칭 알고리즘은 이러한 이분 그래프에서 하나의 노드가 두 개 이상의 간선에 포함되지 않도록 선택할 수 있는 최대 간선의 수를 말한다. (즉, 최대한으로 매칭시킬 수 있는 노드 쌍의 수를 찾는 것이다.)

3. 쾨니그의 정리는 최대 매칭 수 = 최소 꼭짓점 덮개 수라는 정리이다.

여기서 최소 꼭짓점 덮개란 몇 개의 노드를 선택하여 이들과 이 꼭짓점들을 포함하는 간선들을 체크할 때, 모든 간선들이 체크되도록 하는 최소 꼭짓점들의 개수를 말한다.

쾨니그의 정리는 이분 매칭 알고리즘 문제의 일부 상황에 적용이 가능한데, 예를 들어 이분 그래프 상황에서 최소 선택을 통해 모든 간선들이 선택되도록 해야할 때 이 최소 선택 수 = 최대 매칭 수임을 이용하여 그냥 이분 매칭 알고리즘을 돌려서 답을 얻으면 된다.

백준 BOJ 1867번 : 돌멩이 제거

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

N x N 격자에 M개의 돌이 있을 때, 한 번의 연산에서 행 또는 열을 선택하여 그 행이나 열에 있는 돌멩이를 모두 제거할 때, 격자의 모든 돌멩이를 제거하는 최소 연산 수를 구하는 문제이다.

각 행의 번호를 left 노드, 열의 번호를 right 노드라고 할 때, 하나의 돌멩이는 하나의 행과 열을 연결하는 간선으로 나타낼 수 있다.

그러면 하나의 간선은 하나의 행과 열을 이으므로 (행과 행 사이 간선, 열과 열 사이 간선은 당연히 존재하지 않으므로) 이분 그래프가 되고, 최소 노드를 선택하여 모든 간선이 선택되도록 하는 문제로 바뀐다.

여기서 위의 쾨니그의 정리를 사용하여 최대 매칭을 구해주면 그것이 곧 최소 연산 수임을 알 수 있다.

따라서 이분 매칭 알고리즘을 통해 최대 매칭 수를 구해주면 된다.

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

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

    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 ans = 0;

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

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

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

백준 BOJ 2414번 : 게시판 구멍 막기

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

N x M 크기의 격자에 . 또는 * 문자들이 주어지고, 행 또는 열 내에서 같은 방향으로 연속한 * 문자들을 선택할 수 있다고 할 때, 모든 *들이 선택되는 최소 선택 수를 구하는 문제이다.

가로 방향으로 연속한 *들에 번호를 매기고, 세로 방향으로 연속한 *들에 다시 번호를 매긴다.

그럼 하나의 * 문자는 가로 번호와 세로 번호 하나씩을 가진다.

하나의 가로 번호 또는 세로 번호를 선택한다는 것은 그 번호에 소속된 모든 *들을 선택한다고 볼 수 있다.

최소 가로 또는 세로 노드의 선택을 통해 모든 *들을 선택하면 문제가 해결된다.

이것은 쾨니그의 정리에 의해 최대 매칭 수와 같으므로 위에서 가로 번호와 세로 번호를 하나의 *이 간선으로 연결된다고 할 때 최대 매칭 수를 구해주면 된다.

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

    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 rnum = 1;

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            if(v[i][j] == '*') {
                u[i][j] = rnum;

                if(j == M || v[i][j+1] == '.') rnum++;
            }

    rnum--;

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

    for(int i=1; i<=M; i++)
        for(int j=1; j<=N; j++)
            if(v[j][i] == '*') {
                w[j][i] = cnum;

                if(j == N || v[j+1][i] == '.') cnum++;
            }

    cnum--;

    adj.resize(rnum+1);

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

    l.resize(rnum+1, -1);
    r.resize(cnum+1, -1);

    int ans = 0;

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

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

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

백준 BOJ 2188번 : 축사 배정

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

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+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 ans = 0;

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

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

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

위의 풀이 코드와 동일한 코드로 백준 BOJ 11375번 : 열혈강호 문제를 통과할 수 있다.

백준 BOJ 9576번 : 책 나눠주기

문제 난이도 : Gold II

알고리즘 분류 : 이분 매칭

N권의 책을 M명의 학생들에게 한 명당 최대 1권씩 나눠준다고 하고, 각 학생은 a ~ b번 사이의 책을 원한다고 할 때, 최대로 나눠줄 수 있는 책의 수를 구하는 문제이다.

i번째 학생에 대한 입력이 (a_i, b_i)일 때 a_i ~ b_i번 책에 해당하는 노드를 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 T; cin >> T;

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

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

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

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

        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 << ans << "\n";
    }
}

백준 BOJ 1017번 : 소수 쌍

문제 난이도 : Platinum III

알고리즘 분류 : 이분 매칭

N개의 자연수들이 주어졌을 때, 이들을 2개씩 묶어서 합한 값이 모두 소수가 되도록 묶는 방법들 각각에서 첫 번째 수와 매칭되는 수들을 오름차순으로 출력하는 문제이다.

N개의 수에 대응되는 노드들을 만들고, N x (N - 1) / 2개의 쌍 중에서 합이 소수인 것들을 간선으로 연결한다.

그 다음 첫 번째 노드 수에 해당하는 노드를 간선들 중 하나를 선택하여 연결한 뒤, 이 상태에서 이분 매칭을 수행하는 과정을 여러 번 거쳐 가능한 모든 경우를 구하면 된다.

여기서 주의할 점은 동일한 노드가 left, right 모두에 있으므로 모두 매칭되었을 때 매칭의 수가 N/2가 아니라 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);

    vector<bool> p(2001, true);
    p[1] = false;

    for(int i=2; i*i<=2000; i++)
        for(int j=2; i*j<=2000; j++) p[i*j] = false;

    int N; cin >> N;

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

    adj.resize(N);

    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++)
            if(p[v[i] + v[j]]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }

    vector<int> u;

    for(int i=0; i<adj[0].size(); i++) {
        l.clear();
        l.resize(N, -1);

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

        int x = adj[0][i];

        l[0] = x, r[x] = 0;

        int cnt = 1;

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

            vis[0] = vis[x] = true;

            if(f(j)) cnt++;
        }

        if(cnt == N) u.push_back(v[x]);
    }

    if(u.size() == 0) {
        cout << -1 << "\n";
        return 0;
    }

    sort(u.begin(), u.end());

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

백준 BOJ 2191번 : 들쥐의 탈출

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N마리의 들쥐와 M개의 굴의 위치가 2차원 좌표로 주어지고, 각 쥐는 S x V 이하의 거리에 있는 굴로만 들어갈 수 있을 때 굴로 들어가지 못하는 최소 들쥐의 수를 구하는 문제이다.

위의 조건식에 대해 O(NM) 시간에 거리를 체크하여 그래프를 구성해주고, 이분 매칭으로 최대 매칭을 찾아 N에서 빼주면 답이 된다.

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

struct s { double 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, M; cin >> N >> M;

    double S, V; cin >> S >> V;

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

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

    adj.resize(N);

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) {
            double x = sqrt(pow(v[i].x - u[j].x, 2) + pow(v[i].y - u[j].y, 2));

            if(x <= S * V) adj[i].push_back(j);
        }

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

    int ans = 0;

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

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

    ans = N - ans;

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

백준 BOJ 4966번 : Cards

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N개의 카드와 M개의 카드가 주어질 때, 두 카드 더미에서 공약수가 1보다 큰 카드 쌍을 제거해나간다고 할 때, 제거할 수 있는 최대 카드 쌍의 수를 구하는 문제이다.

N과 M이 크지 않으므로, 가능한 모든 쌍에 대해 공약수를 조사하여 간선으로 연결해주고, 그렇게 만들어진 그래프에 이분 매칭을 수행해주면 된다.

#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<int> v(N), u(M);

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

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

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

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

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

        int ans = 0;

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

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

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

백준 BOJ 18138번 : 리유나는 세일러복을 좋아해

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N개의 티셔츠와 M개의 세일러카라가 있을 때 카라의 폭이 티셔츠의 폭 w에 대해 w/2 ~ 3w/4 또는 w ~ 5w/4인 경우에만 하나의 세일러복을 만들 수 있다고 할 때, 만들 수 있는 최대 세일러복의 수를 구하는 문제이다.

N개의 노드, M개의 노드를 이분하여 생각한 뒤 O(NM) 시간에 대해 탐색을 수행하여 세일러복을 만들 수 있는 조건에 해당하는 두 노드 사이만 간선으로 연결해주어 이분 매칭을 수행해주면 된다.

#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<double> v(N), u(M);

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

    adj.resize(N);

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            if((v[i]/2 <= u[j] && u[j] <= v[i]*3/4) || (v[i] <= u[j] && u[j] <= v[i]*5/4)) adj[i].push_back(j);

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

    int ans = 0;

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

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

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

백준 BOJ 10276번 : Jewelry Exhibition

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N x M 격자 내에 실수형 좌표 K개가 주어지고, 하나의 레이저는 행 또는 열 중 [정수, 정수+1] 구간의 모든 좌표를 스캔 가능하다고 할 때, K개의 좌표가 모두 스캔되기 위한 최소 레이저 수를 구하는 문제이다.

정수 x에 대해 [x, x+1) 구간의 모든 점들을 정수 x로 내림하여 기록하면 백준 BOJ 1867번 : 돌멩이 제거 문제의 상황과 동일해지므로 같은 방식으로 풀이하면 된다.

#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, K; cin >> N >> M >> K;

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

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

            adj[(int)x].push_back((int)y);
        }

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

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

        int ans = 0;

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

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

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

백준 BOJ 11180번 : Paintball

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N명의 사람이 있고, M개의 쌍 (a, b)가 주어질 때, a번 사람과 b번 사람이 서로를 paintball로 쏠 수 있다고 하자.

모든 사람이 정확히 하나의 paintball을 맞는 것이 가능한지 판별하고, 가능하다면 i번째 사람이 몇 번 사람을 쏘면 되는지 그 예시를 출력하는 문제이다.

이분 매칭으로 풀이하되 a번 노드를 b번 노드로 연결해주고, b번 노드 또한 a번 노드로 연결해준다. (둘 중 누구라도 서로를 쏠 수 있으므로)

이제 이분 매칭을 해준 뒤 최대 매칭 값이 N인 경우만 답으로 가능하고, 그렇지 않으면 Impossible을 출력해주면 된다.

매칭 값이 N인 경우는 l[i] 값들을 출력해주면 된다. (l[i] : i번째 left 노드에서 연결되어있는 right 노드의 번호)

#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);
        adj[y].push_back(x);
    }

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

    if(ans != N) {
        cout << "Impossible\n";
        return 0;
    }

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

백준 BOJ 11432번 : Candy Bombers

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N명의 파일럿이 각각 M개의 비행기 중에서 운전 가능한 것이 다르다고 할 때, 최대로 운전할 수 있는 비행기의 수를 구하는 문제이다.

파일럿과 비행기 그룹 간의 그래프를 형성하여 이분 매칭을 돌리면 된다.

#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 M, N; cin >> M >> N;

        adj.clear();
        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.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 << "Data Set " << t << ":\n";
        cout << ans << "\n";
        cout << "\n";
    }
}

백준 BOJ 11670번 : 초등 수학

문제 난이도 : Platinum IV

알고리즘 분류 : 이분 매칭

N개의 정수 쌍이 주어지고, 두 정수를 +, -, * 연산 중 하나로 연산하여 모든 연산 값들이 다르게 만드는 것이 가능한지를 구하고, 가능하다면 각 연산식을 모두 구하는 문제이다.

해시맵을 사용하여 각 연산 값들이 중복되지 않게 노드를 형성하여 연결해주고, 이분 매칭을 수행해주면 된다.

문제는 매칭이 모두 가능한 경우 연산 식을 복원해야 하는데, 이를 위해 map을 하나 더 선언해서 각 right 노드가 원래는 어떤 값을 가지고 있었는지를 연결시켜주어 마지막에 출력해주는 방식을 사용하면 구현이 가능하다.

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

    vector<pair<int, int>> v(N);
    map<int, int> m, rm;
    int cnt = 0;

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

        v[i].first = a, v[i].second = b;

        if(m[a+b] == 0) m[a+b] = ++cnt;
        rm[m[a+b]] = a + b;
        adj[i].push_back(m[a+b]);

        if(m[a-b] == 0) m[a-b] = ++cnt;
        rm[m[a-b]] = a - b;
        adj[i].push_back(m[a-b]);

        if(m[a*b] == 0) m[a*b] = ++cnt;
        rm[m[a*b]] = a * b;
        adj[i].push_back(m[a*b]);
    }

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

    int match = 0;

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

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

    if(match != N) {
        cout << "impossible\n";
        return 0;
    }

    for(int i=0; i<N; i++) {
        int a = v[i].first, b = v[i].second;

        char ch;

        if(rm[l[i]] == a + b) ch = '+';
        else if(rm[l[i]] == a - b) ch = '-';
        else if(rm[l[i]] == a * b) ch = '*';

        cout << a << " " << ch << " " << b << " = " << rm[l[i]] << "\n";
    }
}