[백준] 1867 돌멩이 제거

문제 주소 : www.acmicpc.net/problem/1867

1867번: 돌멩이 제거

문제 확인

 

최소 버텍스 커버 문제입니다.

행과 열을 기준으로 이분 매칭 그래프를 작성합니다.

최소 버텍스 커버란 정점, 간선으로 구성된 그래프에서 일부 간선을 선택 시 양 끝점 중 적어도 하나가 포함된 집합을 의미합니다.

 

풀이

 

X _ X
_ X _
_ X _

백준의 예시를 이분 매칭 그래프로 그려보면 다음과 같습니다.

위 그래프에서 최소 버텍스 커버는 {1, 2}가 됩니다. 열 1에서 나오는 간선들을 선택하면 1, 3이 포함되고 행 2에서 나오는 간선을 포함하면 2, 3이 포함되어 최소 버텍스 커버가 됩니다.

 

dfs 탐색마다 매칭을 시키며 처음 1을 탐색 시 1이 매치되고 2를 탐색 시 2가 매치되며 3을 탐색 시 이미 매치가 된 2를 만나게 되어 결과는 2가 됩니다.

 

코드

#include <cstdio>
#include <vector>
#include <memory.h>
using namespace std;
vector <short> graph[501];
short match[501];
bool visit[501];
bool dfs(short i) {
    for (short next : graph[i]) {
        if (visit[next])continue;
        visit[next] = true;
        if (!match[next] || dfs(match[next])) {
            match[next] = i;
            return true;
        }
    }
    return false;
}
int main() {
    int n, k, res = 0;
 
    scanf("%d%d", &n, &k);
    for (short i = 0, s, e; i < k; i++) {
        scanf("%hd%hd", &s, &e);
        graph[s].push_back(e);
    }
    for (short i = 1; i <= n; i++) {
        memset(visit, 0, n+1);
        if (dfs(i))res++;
    }
    printf("%hd", res);
}