[백준]BOJ #1867: 돌멩이 제거

작성일 | In

문제 출처: https://www.acmicpc.net/problem/1867

문제

n행 n열의 격자로 나뉜 운동장이 있다. 이 위에 k개의 돌멩이가 있는데, 하나의 돌멩이는 격자 한 칸에 정확히 들어가 있으며, 두 개 이상의 돌멩이가 한 칸에 들어가 있는 경우는 없다.

사고의 위험을 없애기 위해 이 돌멩이를 모두 제거하고 깨끗한 운동장을 만들려고 한다. 돌멩이를 제거할 때에는, 한 행이나 한 열을 따라 직선으로 달려가면서 그 행이나 열에 놓인 돌멩이를 모두 줍는 방식을 쓴다.

여러분이 할 일은 운동장의 상태가 주어졌을 때 최소 몇 번이나 달려가야 돌멩이 줍기를 끝낼 수 있는지 계산하는 것이다.

입력

첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다.

출력

첫 줄에 몇 번의 달리기를 통해 돌멩이를 주울 수 있는지 출력한다.

예제

입력 1
1
2
3
4
5
3 4
1 1
1 3
2 2
3 2
출력 1
1
2

풀이

입력으로 주어진 그리드를 row와 column으로 이루어진 이분 그래프로 생각하고 돌멩이 위치의 row와 column을 간선으로 이어주자. 이렇게 되면 문제는 그 이분 그래프의 minimum vertex cover 를 구하는 문제로 생각할 수 있다.

Kőnig’s theorem

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

위 쾨닉의 정리를 이용해 만들어준 이분 그래프의 최대 매칭 수를 구해주면 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int N, K;
vector<int> e[MAX];
int rev[MAX];
int visited[MAX];

int t;
void init(){
    cin>>N>>K;
    int r, c;
    foi(K){
        cin>>r>>c;
        e[r].push_back(c);
    }
    memset(visited, 0, sizeof(visited));
    memset(rev, 0, sizeof(rev));
}
int match(int v){
    for(int d:e[v]){
        if(visited[d]||rev[d]==v) continue;
        if(rev[d]){
            visited[d]=1;
            if(match(rev[d])){
                rev[d]=v;
                return 1;
            }
        } 
        else{
            rev[d]=v;
            return 1;
        }
    }
    return 0;
}
void solve(){
    int cnt=0;
    foi(N){
        memset(visited, 0, sizeof(visited));
        match(i);
    }
    foi(N)
        if(rev[i]!=0)
            cnt++;
    cout<<cnt<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    init(); 
    solve();
}

Reference