[C++] 3683번 고양이와 개 - 이분 매칭

1. 문제

• 모든 사용자는 다음 라운드에 진출시킬 동물과 이번 라운드에 떨어뜨릴 동물을 한 마리씩 투표한다. 모든 투표는 고양이 하나와 개 하나로 이루어져 있다. 각 시청자가 자신이 진출하는 동물로 뽑은 동물이 진출하고, 탈락한 동물로 뽑은 동물이 탈락되었을 때 "투표가 반영되었다."라고 한다. PD는 임의로 진출시키고 탈락시킬 동물을 여러 마리 골라 투표가 반영된 시청자 수를 최대화하려고 한다. 이때 최댓값을 구하시오.

<입력>

• -1-   테스트 케이스의 개수 \(T(1 \leq T \leq 100)\)
• --1-   고양이의 수 c, 개의 수 d, 투표한 시청자의 수 v \((1 \leq c, d \leq 100, 0 \leq v \leq 500)\)
• --2~v+1-   각 시청자의 투표정보가 주어진다. 첫 번째는 진출시킬 동물로 뽑은 동물, 두 번째는 탈락시킬 동물로 뽑은 동물. 고양이는 C, 개는 D로 시작하고 그 뒤 숫자는 동물의 번호이며 이는 1이상 c, d 이하이다.

<출력>

• 각 테스트 케이스 마다, 투표가 반영되는 시청자의 최댓값을 구하여라.

2. 재정의

• 각 동물의 진출 여부에 따라 이에 만족하는 사용자의 최대 수를 구하여라.

3. 해결방법

• 사용자들의 투표가 모두 만족한다고 가정했을 때 사용자들의 투표가 서로 충돌하게 된다. 이때 특정 사용자들의 투표를 무시함으로써 이 충돌을 막을 수가 있다. 즉 투표를 무시한 최소 횟수를 투표 횟수에 빼주면 투표가 반영되는 시청자의 최댓값이 되는 것이다.
• 고양이를 좋아하는 사람끼리는 서로 충돌할 수 없으므로 고양이를 좋아하는 사람과 개를 좋아하는 사람끼리 고려하자.
• 사용자들의 투표 결과 중 i번째 시청자의 좋아하는 동물과 j번째 시청자가 싫어하는 동물이 같거나, i번째 시청자의 싫어하는 동물, j번째 시청자가 좋아하는 동물이 같다면 모순이 발생하게 된다. 이를 통해 서로 모순 관계인 시청자들의 의견을 찾을 수 있고 이를 연결하여 고양이를 좋아하는 그룹과, 개를 좋아하는 그룹끼리 나누면 그래프가 만들어진다.
• 이때 모순을 뜻하는 간선을 제거해 충돌을 없애야 하고 이는 최대 유량 및 최소 컷 정리에 의해 최대 유량과 같으므로 이분 매칭을 통해 없애야 하는 간선의 최소수를 구할 수 있다.
• 투표수 - 최대 유량이 투표가 반영되는 시청자의 최댓값이다.

4. 실수한 점, 개선할 점

• 맨 처음에 최대 유량 및 최소 컷 정리를 생각해서 dfs로는 못 풀 것이라고 생각했는데 dfs로 풀 수 있어서 dfs로 바꾸었다.
• 두 동물이 같은지를 비교하는 것은 .compare()매소드를 이용하면 된다.
• 내가 짠 코드를 보면 고양이를 좋아하는 사람과 개를 좋아하는 사람끼리 충돌이 일어나서 결국 간선을 두 번 만들어주게 된다. 이를 간선을 한 번 만드는 것으로 줄일 수 있고 이러면 소요 시간이 줄어든다. 이렇게 코딩한 코드가 있어서 아래에 링크하였다.

 

<코드>

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;
const int MAX_V = 501;

//방향 그래프
vector<int> adj[MAX_V];

//테스트 케이스의 수 T
int T;
//고양이의 수 c, 개의 수 d, 투표한 시청자의 수 v
int c, d, v;
//각 사람의 평가(좋아하는 것, 싫어하는 것)
string eval[MAX_V][2];
//dfs용
int Occupy[MAX_V];
bool done[MAX_V];

void input() {
    for(int i=0; i<MAX_V; i++) {
        adj[i].clear();
        eval[i][0].clear();
        eval[i][1].clear();
    }
    memset(Occupy, 0, sizeof Occupy);
    
    cin >> c >> d >> v;
    
    for(int i=1; i<=v; i++)
        cin >> eval[i][0] >> eval[i][1];
    
    
    //의견이 충돌하는 것끼리 연결시켜주기
    for(int i=1; i<v; i++) {
        for(int j=i+1; j<=v; j++) {
            if(!eval[i][0].compare(eval[j][1]) || !eval[i][1].compare(eval[j][0])) {
                if(eval[i][0][0] == 'C')
                    adj[i].push_back(j);
                else
                    adj[j].push_back(i);
            }
        }
    }
}

bool dfs(int Node) {
    for(auto Next : adj[Node]) {
        if(done[Next])
            continue;
        done[Next] = true;
        if(!Occupy[Next] || dfs(Occupy[Next])) {
            Occupy[Next] = Node;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--) {
        input();
        
        /*
        for(int i=0; i<=v; i++)
            for(auto x : adj[i])
                cout << i << ' ' << x->next << '\n';
        */
        
        //이분 매칭
        int total_flow = 0;
        for(int i=1; i<=v; i++) {
            memset(done, false, sizeof done);
            if(dfs(i))
                total_flow++;
        }
        //충돌이 일어나는 개수만큼 사용자의 의견을 무시하면 된다.
        cout << v-total_flow << '\n';
    }
    return 0;
}

 

 

<참고한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/157033

로그인

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.