[PS] 백준 2188번: 축사 배정

|

문제

내가 이해한 문제 내용

소의 수와 축사의 수가 주어질 때 축사 1개당 소는 1마리 들어갈 수 있다. 또한 소마다 선호하는 축사들이 각각 다른데 이 때 축사에 들어갈 수 있는 최대 소의 마릿수 최댓값을 구하여라.

접근 방식

이분매칭인 걸 알고는 있었지만 까먹었던 터라 안보고 백지에서 시작해보기로 했다.

  • 희망하는 축사개수가 적은 소부터 매칭 → 틀림
  • DFS로 소와 축사 사이를 이동하면서 구하기 → 틀림

꽤 고민을 많이 했지만 DFS에서 더 이상 생각을 할 수 없어서 라이님의 답을 보게 되었다. 핵심 개념은 DFS를 쓰는 것이 맞다.

  • 1번째 소를 비어있는 축사에 배정한다.
  • 2번째 소를 비어있는 축사에 배정하려고 하는데 다 차있다, 그러면 해당 축사에 있는 소를 다른 곳으로 옮기는지 확인한 후에 옮길 수 있으면 옮기고 2번째 소를 이 축사에 배정한다.
  • 이후 위 과정을 반복한다.

DFS가 쓰이는 부분은 축사에 있는 소가 다른 축사로 이동하는지 확인할 때이다. 다시 똑같은 알고리즘을 반복해야 하기 때문에 재귀를 써야 하는 것.

어려웠던 점 & 배운 점

DFS로까지 접근을 했었는데 그 이후에 발전을 하지 못한 점이 아쉬웠고 소와 축사를 어떻게 매칭시킬지 구현하는 부분이 어려웠다. 처음엔 개념만 확인하고 풀어보려 하였으나 개념으로는 구현이 안돼서 시간을 많이 쓰게 되었다. 또한 이런 DFS 응용문제에 약하다는 것을 다시 깨달았다.

시간복잡도

$V$개의 정점에 대해서 DFS를 사용하니까 $O(V*(V+E))=O(VE)$

코드

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int n,m,s,num,ans;
int cowToHome[201],homeToCow[201],visited[201];
vector<int> adj[201];


bool dfs(int v)
{
    visited[v] = 1;
    // 소가 갈 수 있는 축사들 체크
    for(int i=0; i<adj[v].size(); i++){
        int home = adj[v][i];
        // 1. 축사가 비어있는 경우
        // 2. 축사가 차있지만 해당 소가 다른 축사로 이동할 수 있는 경우
        // visited[homeToCow[home]]을 체크하는 이유는 자기 자신으로 이동할 수 있기 때문
        if(!homeToCow[home] || !visited[homeToCow[home]] && dfs(homeToCow[home])){
            homeToCow[home] = v;
            cowToHome[v] = home;
            return true;
        }
    }
    return false;
}

int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++){
        scanf("%d",&s);
        while(s--){
            scanf("%d",&num);
            adj[i].push_back(num);
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++){
        // 소가 축사에 들어가지 못한경우
        if(!cowToHome[i]){
            memset(visited,0,sizeof(visited));
            // 소가 축사에 들어갔으면 증가
            if(dfs(i)) ans++;
        }
    }
    printf("%d",ans);

    return 0;
}