글 읽기 - 이분 매칭을 살짝 변형해서 코드를 짰는데 맞는 로직인가요?

ploffer11 5년 전 0

먼저 에드몬드 카프를 사용해 최대유량으로 문제를 한번 풀었고,

이분 매칭 코드를 살짝 변형시키면 풀 수 있지 않을까 해서

한쌍의 이분 매칭을 찾는 코드를 이것저것 건드리다가 ac를 받아버렸습니다.

하지만 이게 맞는 로직인지 몰라 질문을 드립니다.

groupA 는 pair<int, int>를 저장하며, first와 second에 할 수 있는 일을 저장합니다.

dfs는 a의 넘버와 k를 받는데, k가 1일 경우 groupA의 first를, 2일 경우 second를 갱신하려 하는데, groupA가 할 수 있는 일을 이미 다른 groupA의 팀원이 하고 있으면 groupA의 팀원의 첫번째 일이나 두번째 일을 갱신을 시도해 갱신되면 true를 반환합니다.

제대로 된 로직으로 푼건가요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
typedef pair<int, int> pii;

vector<int> graph[1005];
pii groupA[1005];
int groupB[1005];
bool visit[1005];

int n, m, t, x;

bool dfs(int a, int k)
{
	visit[a] = true;

	for ( auto b : graph[a] )
	{
		if ( groupB[b] == 0 || (!visit[groupB[b]] and (dfs(groupB[b], 1) || dfs(groupB[b], 2))) )
		{
			groupB[b] = a;
			if ( k == 1 )
			{
				groupA[a].first = b;
			}
			else
			{
				groupA[a].second = b;
			}
			return true;
		}
	}
	return false;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;

	for ( int i = 1; i <= n; i++ )
	{
		cin >> t;
		while ( t-- )
		{
			cin >> x;
			graph[i].push_back(x);
		}
	}

	int ans = 0;
	for ( int i = 1; i <= n; i++ )
	{
		if ( dfs(i, 1) ) ans++;
		fill(visit, visit + 1005, false);
		if ( dfs(i, 2) ) ans++;
		fill(visit, visit + 1005, false);
	}

	cout << ans;
}

ploffer11 5년 전 1

제가 검토를 해봤는데 이 코드는 로직은 완벽히틀린 코드입니다..

왜냐면 A그룹의 1번이 B그룹의 1, 2, 4를 가르킬 수 있고

(1, 1)과 (1, 2)를 매칭한 후 A그룹의 2번이 B그룹의 2번과 매칭을 시도했을 때, 제 코드는 (1, 2) 매칭을 바꾸는 게 아니라 (1, 1) 매칭을 (1, 4)로 바꿔버립니다.

즉 (1, 2) (1, 4) (2, 2) 로 매칭이 되어있는 이상한 상태가 됩니다.

그러나 이 로직의 헛점을 저격하는 테스트 케이스를 만들면 ..

예를 들어 A그룹의 3번이 B의 1번을 가르키게 하면, B의 1번은 매칭된 상대가 없으므로 바로 매칭이 되어

(1, 2) (1, 4) (2, 2) (3, 1) 로 매칭이 되어 답이 4로 나올.. 것 같은데 이게 또 3이 잘 나옵니다.

이는 groupB[1]값이 잘못된 풀이로 인해 여전히 1로 남아있기 때문인데... 이걸 어떻게 저격해야할지 정말 감도 안잡힙니다.

반례 찾기에 자신있는 분은 도전해 보셔도 좋습니다.

댓글을 작성하려면 로그인해야 합니다.