[BOJ 3295] 단방향 링크 네트워크

이분 매칭 문제

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

 

 

---

[문제 풀이]

 

결론부터 말하면 그냥 이분 매칭 문제입니다.

모든 노드에 대한 연결 관계를 간선으로 추가한 후에 최대 매칭을 구하면 됩니다.

이게 왜 평범한 이분 매칭 문제인지 설명해 보겠습니다.

 

---

이 문제를 설명하기에 앞서 상어의 저녁 식사와 결이 비슷하여 먼저 설명하겠습니다.

상어 문제는 상어가 서로 먹을 수 있는 관계가 주어졌을 때 서로 먹을 수 있는 최댓값을 구하는 문제입니다.

모든 상어를 이분 그래프 양쪽 집단에 전부 배치하고 먹을 수 있는 관계로 간선을 그어주면 이분 매칭 문제라는 걸 알 수 있습니다.

그런데 이미 먹힌 상어가 다른 상어를 먹을 수 없다는 조건이 붙어있습니다.

 

이 조건을 해결하는 핵심은 우선 매칭을 하고 상어가 먹은 시점을 조정하는 것입니다.

 

1번부터 7번까지 상어가 있고, 관계가 아래와 같다고 생각해 봅시다.

 

• 1 → 5
• 2 → 4
• 5 → 3
• 6 → 1 (5가 이미 먹음)
• 5 → 7

위와 같은 관계가 형성되었을 때, 첫 번째(1 → 5)에서 5가 이미 먹혔으므로 과연 세 번째(5 → 3)와 다섯 번째(5 → 7)에서 상어 5가 3, 7을 먹을 수 없을까요?

 

우리는 첫 번째부터 봤지만 상어들이 먹고 먹힌 순서는 우리가 본 순서와 무관합니다.

우리는 이분 매칭을 사용하여 위와 같이 일단 처리해 놓고, 상어들은 '5가 3과 7을 이미 먹은 후에 1이 5를 먹었다.'라고 끼워 맞추면 되는 겁니다.

 

물론 이 문제는 변수가 하나 더 남아 있지만 상어 문제는 여기까지 얘기하고

우리는 시점을 조정했다는 아이디어만 빌려오겠습니다.

 

---

이 문제에서는 혼동을 주기 위해 선형으로 링크된 k개 노드의 가치가 k - 1, 원형으로 링크된 k개 노드의 가치가 k... 이런 식으로 작성했지만 뜯어보면 간단합니다.

 

1부터 4까지 4개의 노드가 있다고 가정하면

 

• 1 (선형, 가치: 0달러 == 링크 0개)
• 1 → 3 (선형, 가치: 1달러 == 링크 1개)
• 1 → 3 → 2 (선형, 가치: 2달러 == 링크 2개)
• 1 → 3 → 2 → 4 (선형, 가치: 3달러 == 링크 3개)
• 1 → 3 → 2 → 4 → 1 (원형, 가치: 4달러 == 링크 4개)

선형으로 링크가 됐든, 원형으로 링크가 됐든 링크의 개수가 가치가 되는 겁니다.

 

즉, 본 문제는 조건(링크 시 한 노드 당 들어오고 나가는 간선이 최대 한 개)에 맞게 링크의 개수의 최댓값을 구하는 문제로 바뀌었습니다.

모든 노드를 이분 그래프 양쪽 집단에 전부 배치하고 연결할 수 있는 관계로 간선을 그어주면 이분 매칭 문제라는 걸 알 수 있습니다.

 

관계가 아래와 같이 나왔으면

 

• 1 → 3
• 4 → 1
• 2 → 5
• 5 → 4
• 6 → 1
• 4 → 5

2 → 5 → 4 → 1 → 3 (선형)

4 → 5 → 4 / 6 → 1 → 3 (원형 / 선형)

 

조건에 맞게 링크를 걸면 위 두가지 결과가 나옵니다.

상어 문제처럼 이분 매칭으로 우선 링크(매칭)를 걸고 링크가 어떻게 걸렸는지는 어떻게든 끼워맞추는 겁니다.

 

이런 류의 문제를 방향 그래프에서 최소 체인을 찾는 문제라고 하고 이분 매칭으로 푼다고 알고 있으면 됩니다.

 

---

[소스 코드] / C++

 

#include <iostream>
#include <vector>

using namespace std;

int N;
int B[1000];
vector<int> adj[1000];
bool visited[1000];

void BtR() {
    for (int i = 0; i < 1000; i++) {
        B[i] = -1;
        adj[i].clear();
    }
}

void setVisited() {
    for (int i = 0; i < 1000; i++) {
        visited[i] = false;
    }
}

bool dfs(int a) {
    visited[a] = true;

    for (int b : adj[a]) {
        if (B[b] == -1 || !visited[B[b]] && dfs(B[b])) {
            B[b] = a;
            return true;
        }
    }

    return false;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T; cin >> T;
    while (T--) {
        BtR();
        cin >> N;
        int M; cin >> M;
        
        while (M--) {
            int u, v; cin >> u >> v;

            adj[u].push_back(v);
        }

        int ans = 0;

        for (int i = 0; i < N; i++) {
            setVisited();
            if(dfs(i)) ++ans;
        }

        cout << ans << '\n';
    }

    return 0;
}