백준)1864 - 돌멩이 제거

문제 링크 :  https://www.acmicpc.net/problem/1867

1867번: 돌멩이 제거

문제

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

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

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

입력

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

출력

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

힌트

돌멩이가 있는 곳은 X, 없는 곳은 _으로 표현하면 입력은 다음과 같다.

X _ X
_ X _
_ X _

1행을 따라 달리며 (1,1), (1,3)에 위치한 돌멩이를 줍는다. 2열을 따라 달리며 (2,2), (3,2)에 위치한 돌멩이를 줍는다. 두 번의 달리기로 작업을 완료할 수 있다.

풀이>>

힌트에 답이 있다. 처음에 고민을 진짜 많이 했다. 각 행과 열을 탐색해서 우선순위 큐를 이용하여 돌멩이가 가장 많은 행 또는 열을 우선순위적으로 건너가면서 방문했다는 표시를 하는 방법으로 풀어야 하는 등등... 하지만 생각을 하면 할수록  행이 우선순위? 열이 우선순위? 어딜 먼저 가든 정돈된 방법이 아니었다. 미궁이었다.  이문제가 이분 매칭 알고리즘 분류라는 점을 곰곰이 생각해 보았다. 이문제는 노트북 주인을 찾아 주는 문제와 동일한 문제였다 row 열 이 사람이고 col 열이  노트북이라고 생각하면 된다. 

row [1] 은 col [1]과 col [3]으로 갈 수 있다.

row [2] 은 col[2] 로 갈 수 있다.

row [3] 은 col[2] 로 갈 수 있다. 

 

---> 해석을  해보면

row[1]은 col [1]로 가면 끝이다 ans++ ;       ans = 1;

 

row [2]은 col [2]로 가면 끝이다 ans++ ;       ans = 2;

 

row[3]은 col [2]로 가고 싶어 한다. 이때! col [2] 은 row [2]가 소유하고 있으므로 row [2]가 다른 경로로 갈 수 있는 지확인해 보지만 갈 수 있는 길이 없다. row [3] 은 갈 수 있는 길이 없다 고로 ans는 변하지 않는다. 

하지만 돌멩이를 줍는 이미지를 생각해 보자 row [2]로 col [2]를 해결했다면 row [3]으로 col [2]를 다시 가서 돌멩이를 또 주울 이유가 없다! 결국 그래프 문제를 돌멩이로 문제를 만든 것이다. 

 

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
 
int d[501];
int visited[501];
vector<int> a[501];
 
int dfs(int x) {
 
        int i;
 
        for( i = 0 ; i < a[x].size() ; i++) {
                int y = a[x][i];
 
            if(visited[y]) continue;
 
                visited[y] = 1;
 
 
                if(d[y] == 0 || dfs(d[y])) {
 
                    d[y] = x;
 
                    return 1;
 
                }
 
        }
 
        return 0;
}
 
int main()
{
    int i,j;
    int N , M;
 
    cin >> N >> M;
 
    int x,y;
    for( i=1; i<= M ; i++) {
 
            cin >> x >> y;
            a[x].push_back(y);
 
    }
 
    int ans = 0;
 
    for(i=1; i<= N ; i++) {
        memset(visited,0,sizeof(visited));
        if(dfs(i)) ans++;
 
    }
 
    cout << ans;
 
    return 0;
}