[백준/BOJ] 1867번 : 돌멩이 제거 (이분 매칭, 쾨니그의 정리)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1867번 : '돌멩이 제거' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum III 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘과 쾨니그의 정리에 대한 이해가 필요합니다. (다만, 쾨니그의 정리에 대해서는 이 포스트에서 다룰 것입니다.)

 

 

1867번 : 돌멩이 제거

1867번: 돌멩이 제거

 

격자판 구조에 K개의 돌멩이가 있고 한 행이나 열을 선택하여 그 행이나 열에 있는 돌멩이를 한 번에 모두 제거할 수 있다고 할 때, 최소 몇 번의 선택으로 모든 돌멩이를 제거할 수 있는지를 구하는 문제입니다.

 

이분 매칭 문제로 분류가 되어있기 때문에 행과 열을 두 그룹으로 구성하여 노드를 간선으로 연결하는 것은 유추할 수 있지만, 최소 행이나 열의 선택 수를 구하는 방법을 어떻게 구할지 생각하기는 어렵습니다.

 

여기서는 쾨니그의 정리를 알아야 하는데, 쾨니그의 정리란 이분 그래프에서 모든 간선을 선택할 수 있도록 하는 최소 꼭짓점의 수 = 최대 매칭 수라는 정리입니다.

여기서 꼭짓점으로 간선을 선택한다는 것은, 꼭짓점을 선택했을 때 그 꼭짓점과 연결되어있는 모든 간선들을 선택함을 의미합니다.

 

쾨니그의 정리를 알았다면 이 문제에서 모든 돌멩이를 줍기 위해(= 모든 간선을 선택하기 위해) 최소 꼭짓점을 선택해야 하는데 이 개수는 최대 매칭 수와 같음을 알 수 있으므로 단순히 이분 매칭을 수행하여 매칭 수를 출력해주면 됩니다.

 

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

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

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 N, K; cin >> N >> K;
    while(K--) {
        int x, y; cin >> x >> y;
        Adj[x].push_back(y);
    }

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

    cout << match;
}

 

구현 자체는 일반적인 이분 매칭 문제와 같습니다.

간단한 정리를 이용하여 쉽게 풀어볼 수 있는 이분 매칭 응용 문제였습니다.

 

 

 

위의 풀이대로 코드를 작성하여 제출하면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.