[C++] 백준 1867번 - 돌멩이 제거

📖 문제

 

📋 코드

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int n, k, ans;
bool visited[501];
int bm[501]; // Bipartite Matching
vector<vector<int>> grid(501);

bool DFS(int row)
{
    if (visited[row]) // 이미 방문한 노드
        return false;
    visited[row] = true;

    for (int i = 0; i < grid[row].size(); i++)
    {
        int column = grid[row][i];
        // 매칭이 되어있지 않거나
        // 해당 column과 매칭되어있는 다른 row가 매칭되었을 때
        if (bm[column] == 0 || DFS(bm[column]))
        {
            bm[column] = row; // 매칭시키기
            return true;      // 매칭완료
        }
    }

    return false;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        grid[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
    {
        memset(visited, false, n + 1);
        if (DFS(i))
            ans++;
    }
    cout << ans << '\n';
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

처음에 문제를 접했을 때는 각 행별로 열 별로 돌의 수를 저장해서 수가 가장 많은 곳부터 돌을 지워나가는 Greedy 한 방식으로 풀이를 하였습니다.

그러나 아래와 같이 같은 수가 많은 상황에서 어느 행을 혹은 열을 먼저 지우는지에 따라 돌을 줍는 횟수가 3번이 될 수도, 4번이 될 수도 있기 때문에 다른 방식으로 풀이를 해야 했습니다.

 

📚 필요한 사전 지식

최대 이분 매칭 (Maximun bipartite grape)

네트워크 플로우의 한 종류로 이분 그래프에서 최대 매칭(최대로 효율적인 연결관계)을 구하는 알고리즘입니다. 여기서 최대 매칭은 모든 노드들이 다른 집단의 노드들을 연결하는 최대 매칭을 의미합니다.
(이분 그래프 : 정점을 두 그룹으로 나눴을 때 모든 간선에 연결된 두 정점이 서로 다른 그룹에 존재하는 그래프)

이해를 돕기 위해!
위와 그림과 같이 지원자들(Applicants)이 있고 각각 지원하게 되는 직무(Jobs)가 있다고 했을 때 정부에서(?) 취업을 장려하기 위해 구직자가 최대한 취업을 하는 방향으로 매칭 시키기 위해서는 오른쪽과 같이 최대 매칭을 잡아줄 수 있습니다. 이분 매칭 알고리즘 자체가 서로서로 양보해서 매칭을 최대한으로 잡게 하는 것이 핵심입니다.

 

최소 버텍스 커버 (Minimum vertex cover)

어떤 그래프 G에서 정점들의 집합을 S라고 할 때 S의 부분집합 S'를 선택하여 G의 모든 간선이 S'에 속한다면 이를 Vertex cover(정점 덮개)라고 부릅니다. 이때, 최소한의 정점만으로 이러한  Vertex cover를 만족할 수 있다면, 이를 최소 버텍스 커버(Minimum vertex cover)라고 합니다.

쉽게 말해, 그래프에서 선택된 정점들에 인접한 간선들이 활성화된다고 할 때 모든 간선을 활성화시키는 정점의 집합을 버텍스 커버라고 하고, 오른쪽에서 정점 1과 정점 2를 선택 시 모든 간선을 활성화시키므로 정점 1과 2는 최소 버텍스 커버입니다. 

 

쾨니그의 정리 (Kőnig's theorem)

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory) 

=> "모든 이분 그래프에서 최대 매칭의 수는 최소 버텍스 커버 수와 같다."

 

 

🤔 돌멩이를 줍는 거랑 이분 매칭, 최소 버텍스 커버,,,, 먼 상관이지..?

각각의 정점은 행과 열을 뜻하고 간선은 돌멩이를 뜻하는 이분 그래프를 그려볼 수 있습니다.

 

여기서 최대 이분 매칭을 통해서 최대 매칭 수를 구할 수 있게 되고,

쾨니그의 정리에 의해 최대 매칭 수 == 최소 버텍스 커버 수 임을 알 수 있습니다.

그리하여 모든 간선(돌멩이)이 최소 버텍스 커버에 속하게 되므로

최소 버텍스 커버 수가 곧 돌멩이를 줍는 직선 달리기 최소 횟수를 의미하게 됩니다.
(저도 문제를 풀고 나서도 이해를 하는데 좀 시간이 걸렸습니다...) 

 

 

🐞 풀이 시뮬레이션

1번 열 노드에 아무런 매칭이 되어있지 않으므로 1번 행 노드와 1번 열 노드를 매칭 합니다. 
매칭 되었으므로 다음 행 노드인 2번으로 넘어갑니다.

 

2번 행 노드는 1번 열 노드와 매칭 되기 위해서 이미 매칭 되어있던 1번 행 노드에게 양보(...?)를 부탁합니다.
DFS로 1번 행 노드가 매칭 될 수 있는 열 노드를 찾아서 1번 행 노드는 3번 열 노드와 매칭 되고
2번 행 노드는 1번 열 노드와 매칭 됩니다. 
매칭 되었으므로 다음 행 노드인 3번으로 넘어갑니다.

 

3번 행 노드는 아무런 열 노드와 연결되어 있지 않으므로 다음 행 노드로 넘어가고,
4번 열 노드가 아무런 매칭이 되어있지 않기 때문에 4번 행 노드와 4번 열 노드가 매칭 됩니다.

 

 

🔗 링크

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

1867번: 돌멩이 제거

 

 

📝 비슷한 문제

https://cocoon1787.tistory.com/814

[C++] 백준 11375번 - 열혈강호