[백준/BOJ] 17402번 : 시간 끌기 (이분 매칭, Platinum IV)

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

 

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

 

 

17402번 : 시간 끌기

17402번: 시간 끌기

 

N×M 크기의 격자판에서 K개의 x자 표시가 있는 부분이 선택한 행과 열의 교차점이 되지 않도록 최대한 많이 선택할 수 있는 행과 열의 수를 구하는 문제입니다.

 

x 표시가 되어있는 하나의 행 또는 열에 대해서 그 행 또는 열은 선택하지 않는다고 결정한다면, 그 행 또는 열에 있는 또 다른 x 표시에 대해서는 고려를 할 필요가 없습니다.

예를 들어 2행 2열과 2행 3열에 x 표시가 있을 때, 2행 2열에 있는 x 표시를 선택하여 2행은 선택하지 않겠다고 결정한다면, 2행 3열에 있는 x 표시는 2행을 선택하지 않겠다는 결정을 고려할 필요가 없다는 것입니다.

이런 방식으로 생각해보면 각 행에 대응되는 노드들과 각 열에 대응되는 노드들을 두 그룹으로 나누고 x 표시가 되어있는 행과 열을 간선으로 연결한 뒤 최대 몇 개의 선택하지 않을 행 또는 열을 고려해야 하는지를 이분 매칭으로 확인해 볼 수 있습니다.

매칭이 되지 않은 행과 열은 모두 선택할 수 있으므로, 행 + 열 - 최대 매칭 수가 답이 됩니다.

 

 

문제에서 주어진 예제를 살펴봅시다.

x 표시가 되어있는 행과 열을 간선으로 연결한 뒤, 최대한 많은 매칭을 시켜보면 4쌍의 매칭이 구성됩니다. (빨간색으로 표시된 간선들)

2행 1열의 x가 선택되었으므로, 2행 또는 1열을 선택하지 않도록 선택지에서 지울 수 있습니다. (이 역시 보드에서 빨간색 선으로 표시함)

마찬가지로 3행 2열의 x에 대해 3행 또는 2열을 선택하지 않도록 지울 수 있습니다.

4행 3열과 1행 4열의 x에 대해서도 마찬가지로 빨간색으로 지워주면, 남은 파란색 행 또는 열에 대해서는 (여기서는 행만 남게 되었지만) 모두 선택할 수 있는 것이므로, 답은 4+4(행+열) - 4(빨간색으로 지워진 매칭된 간선들의 수) = 4가 됩니다.

 

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

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

vector<int> Adj[MAX];
int N, M, K;
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);

    cin >> N >> M >> 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 << N + M - match;
}

 

이를 코드로 구현하면 위와 같이 됩니다.

문제를 이분 매칭의 조건으로 대입시키는 과정은 아이디어를 떠올리기 비교적 어렵지만, 코드로 구현하는 것은 이분 매칭 알고리즘에 그대로 대입만 시켜주면 됩니다.

 

 

 

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