[백준] 1867 돌멩이 제거 + 최소 버텍스 커버 문제 (복습)
문제
n행 n열의 격자로 나뉜 운동장이 있다. 이 위에 k개의 돌멩이가 있는데, 하나의 돌멩이는 격자 한 칸에 정확히 들어가 있으며, 두 개 이상의 돌멩이가 한 칸에 들어가 있는 경우는 없다.
사고의 위험을 없애기 위해 이 돌멩이를 모두 제거하고 깨끗한 운동장을 만들려고 한다. 돌멩이를 제거할 때에는, 한 행이나 한 열을 따라 직선으로 달려가면서 그 행이나 열에 놓인 돌멩이를 모두 줍는 방식을 쓴다.
여러분이 할 일은 운동장의 상태가 주어졌을 때 최소 몇 번이나 달려가야 돌멩이 줍기를 끝낼 수 있는지 계산하는 것이다.
입력
첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. 입력으로 주어지는 돌멩이의 위치는 중복되지 않는다.
출력
첫 줄에 몇 번의 달리기를 통해 돌멩이를 주울 수 있는지 출력한다.
문제 이해가 어렵습니다...
X _ X
_ X _
_ X _형태의 돌멩이를 제거한다고 할때,
1행의 줄을 지우면 1행 1열과 1행 3열의 돌멩이 2개를 제거할 수 있습니다.
2행의 줄을 지우면 2행 2열의 돌멩이 하나를 제거할 수 있습니다.
3행의 줄을 지우면 3행 2열의 돌멩이 하나를 제거할 수 있습니다.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
2024-9-27
복습을 하면서 이분 그래프를 왜 그려야하는지 까먹었습니다.
가로,또는 세로 방향으로 움직이면서 돌을 줍는데 최소한의 횟수로 돌을 주어야 하는 상황입니다.
이때 가로1번으로 돌을 한번 주우면 세로 1번과 세로3번은 더이상 가지 않아도 됩니다.
가로 2번으로 돌을 주우러 가면, 세로 2번엔 여전히 돌이 남아있기 때문에 가로 3번도 돌을 주우러 가야합니다.
따라서 이를 이용해서 이분 그래프를 그릴 수 있습니다.
왼쪽은 가로 3개 행, 오른쪽은 세로 3개 열이라고 할때, 가로행 하나에 대해서 주울 수 있는 세로열의 위치를 잇습니다.
가로행 1과, 세로열2를 선택하면 모든 돌을 주울 수 있다는 뜻이고
이게 최소버택스 문제입니다.
한 그래프 위에서 최소의 정점을 골라야하는데, 이게 이분 그래프 위에서 최소버텍스 문제가 나온다면 해결방법은
쾨닉의 정리를 이용할 수 있습니다.
이분 그래프 위에서 최소버택스의 개수는 이분매칭의 개수와 같습니다.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
이를 바탕으로 이분그래프를 그리면 다음과 같습니다
이제 해야할 것은 모든 들어오는 간선이 존재하는 열에 대해(오른쪽 정점들)행에서 열을 연결을 해야하는데, 최소한의 행을 사용해야 합니다.
위에서 답은 1행 1열을 연결하고 1행3열을 연결, 그리고 2행2열을 연결하면 2개의 행 정점에서(1,2행) 모든 열의 정점과 연결할 수 있습니다.
가장 적은수의 정점에서 가능 한 모든 정점에 연결해야합니다.
최소 버텍스 커버 문제라고 합니다.
쾨닉의 정리에 의해 최소 버텍스 커버를 만족하는 정점의 개수는 최대 이분매칭의 개수와 같다고 합니다.
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, K, a, b, cnt, v[501], s[501];
vi adj[501];
bool dfs(int k) {
for (auto r : adj[k]) {
if (v[r])continue;
v[r] = 1;
if (!s[r] || dfs(s[r])) {
s[r] = k;
return true;
}
}
return false;
}
int main() {
FAST;
cin >> N >> K;
while (K--) {
cin >> a >> b;
adj[a].push_back(b);
}
REP(i, N) {
mset(v);
if (dfs(i))cnt++;
}
cout << cnt;
}