[백준/BOJ] 3295번 : 단방향 링크 네트워크 (이분 매칭, Platinum II)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 3295번 : '단방향 링크 네트워크' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다.

 

 

3295번 : 단방향 링크 네트워크

3295번: 단방향 링크 네트워크

 

주어진 그래프를 선형 또는 링 형태의 그래프로만 구성되도록 분해한 뒤 그 때 가지는 간선의 수가 최대가 되도록 할 때, 그 크기를 구하는 문제입니다.

선형 그래프와 링 그래프만 남긴다는 것은 곧 특정 노드에 2개의 간선이 모이거나 2개의 간선이 나가는 일이 없다는 것을 의미합니다.

 

간선의 시작점을 왼쪽 그룹의 노드, 간선의 끝점을 오른쪽 그룹의 노드로 놓고 이분 매칭으로 생각하면 아주 쉽게 해결될 수 있는 문제입니다. (다만 위의 문제를 보고 바로 이분 매칭을 떠올리기는 쉽지 않을 것입니다.)

 

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;

vector<int> Adj[MAX];
int Left[MAX], Right[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=0; i<Adj[from].size(); i++) {
        int to = Adj[from][i];
        if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
            Left[from] = to, Right[to] = from;
            return true;
        }
    }
    return false;
}

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

    int T; cin >> T;
    while(T--) {
        for(int i=0; i<MAX; i++) vector<int>().swap(Adj[i]);

        int N, M; cin >> N >> M;
        while(M--) {
            int from, to; cin >> from >> to;
            Adj[from].push_back(to);
        }

        int match = 0;
        fill(Left, Left+MAX, -1), fill(Right, Right+MAX, -1);
        for(int i=0; i<N; i++) {
            fill(Visit, Visit+MAX, false);
            if(DFS(i)) match++;
        }

        cout << match << "\n";
    }
}

 

구현 자체도 아주 간단한 이분 매칭 코드 수준입니다.

다만 아이디어를 떠올리는 난이도를 높게 쳐서 Platinum II 티어에 배정이 된 것 같습니다.

 

 

 

풀이 코드를 제출하면 위의 기록으로 통과할 수 있습니다.