[백준/BOJ] 2414번 : 게시판 구멍 막기 (이분 매칭, 쾨니그의 정리)

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

 

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

 

 

2414번 : 게시판 구멍 막기

2414번: 게시판 구멍 막기

 

좌표에 주어진 구멍을 구멍이 아닌 칸은 막지 않으면서 일자 모양의 테이프들로 막을 때, 최소 몇 개의 테이프로 구멍을 모두 막을 수 있는지 구하는 문제입니다.

이런 문제들은 근본적인 원리로 접근하는 것도 물론 좋지만, 그게 어렵다면 예시를 몇 가지 그려보면서 규칙성을 발견하는 편이 좋습니다.

 

 

 

예제를 보면서 풀이의 원리에 대해 설명해보겠습니다.

우선 테이프는 가로와 세로 두 방향으로만 붙일 수 있으며, 구멍이 있는 길이에 맞게 최대한 늘려서 붙여야합니다.

그렇기 때문에 테이프의 후보가 될 수 있는 구멍들의 번호를 매기되, 가로와 세로를 구분하여 배열에 저장합니다. (이분 매칭에 사용하기 위함)

이후 행과 열에 대한 테이프 번호에 대해서 이분 매칭을 수행하면서 하나의 구멍이 가지는 서로 다른 번호를 하나의 간선으로써 정보를 저장합니다.

그렇게 된다면 행과 열 관계없이 특정 노드를 최소한으로 골라 모든 간선을 선택하도록 하면 답이 됩니다.

그리고 이것은 쾨니그의 정리에 의해 최대 매칭의 수와 같게 됩니다.

따라서 이 문제를 이분 매칭으로 풀이할 수 있게 되는 것입니다.

 

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1255, MSIZE = 55;

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, M;
    cin >> N >> M;

    char Map[MSIZE][MSIZE];
    for(int i=1; i<=N; i++) {
        cin.clear();
        for(int j=1; j<=M; j++) cin >> Map[i][j];
    }

    int cnt = 1, rCnt;
    int rowHole[MSIZE][MSIZE] = {}, colHole[MSIZE][MSIZE] = {};
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            if(Map[i][j] == '*') {
                rowHole[i][j] = cnt;
                if(j == M || Map[i][j+1] == '.') cnt++;
            }
    rCnt = cnt, cnt = 1;
    for(int i=1; i<=M; i++)
        for(int j=1; j<=N; j++)
            if(Map[j][i] == '*') {
                colHole[j][i] = cnt;
                if(j == N || Map[j+1][i] == '.') cnt++;
            }

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            if(Map[i][j] == '*') Adj[rowHole[i][j]].push_back(colHole[i][j]);

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

    cout << match;
}

 

풀이 코드는 위와 같으며, 일반적 이분 매칭의 코드와 같습니다.

다만 입력 부분에서 예제는 잘 돌아가는데 틀리는 경우가 많을텐데, 입력 버퍼를 반드시 clear 해주고 문자를 입력받는 것을 권장합니다.

저도 예제 입출력은 똑같은데 오답 처리가 반복적으로 되어서 입력부 코드를 수정했더니 정답 처리를 받을 수 있었습니다.

 

 

 

풀이 코드를 제출하면 위와 같이 정답 처리를 받을 수 있습니다.