글 읽기 - 왜 틀린건지 모르겠습니다..

gowithmylord 7년 전 0

dfs방식을 이용해서 이분매칭을 시도했는데,

어느 부분이 잘못된걸까요?

아무리 봐도 모르겠습니다..

#include<iostream>
#include<algorithm>

using namespace std;

int cow_in[201] = {0,};
int cow_done[201] = {0,};
int match[201][201]={0,};

bool find_place(int cow_num){
	if(cow_done[cow_num])
		return false;//이 소에 대한 탐색을 이미 완료한 경우
	cow_done[cow_num] = 1;
	for(int i=1;;i++){
		if(match[cow_num][i] == 0)
			break;
		int target_place = match[cow_num][i];//이 소가 선호하는 i번째 축사 번호를 저장한다
		if(cow_in[target_place] == 0 || find_place(cow_in[target_place])){
			cow_in[target_place] = cow_num;//해당 축사가 비어있거나, 이미 들어가 있던 소가 다른 축사에 들어가도 되면 이 소를 넣는다.
			return true;
		}
	}
	return false;//이 소가 선호하는 축사에 다 못 들어간 경우
}
int main(){
	int n,m,cnt=0;
	scanf("%d %d",&n,&m);
	int i,j,temp;
	for(i=1;i<=n;i++){
		scanf("%d",&temp);
		for(j=1;j<=temp;j++){
			scanf("%d",&match[i][j]);
		}
	}
	for(i=1;i<=n;i++){
		if(find_place(i))
			cnt++;
	}
	printf("%d",cnt);
}

gowithmylord 7년 전 0

아...visited역할인 cow_done행렬을 그다음 소가 find_place를 호출할때마다 초기화해줘야하는군요...

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

문제

문제

출처

ICPC

왜 틀린건지 모르겠습니다..

gowithmylord 7년 전 0

gowithmylord 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말