글 읽기 - 축사배정문제 왜 틀린지 모르겠습니다. 도와주세요

qhy0806 5년 전 0

안녕하세요! 고수님들

2188번을 이분매칭으로 풀었으나 계속 틀렸다고 뜹니다. ( 예제는 정상결과 출력합니다.)

data[i][j]에서 i는 축사를 뜻하고 j는 방을 뜻합니다.

if(data[i][j] == 1 ) 라는 뜻은 i번째 축사가 j 번째 방을 선호하는지 확인하는 것입니다.

그 후, 이미 방에 들어 간 사람이 없거나 or 이미 방에 들어가있는 경우 자리를 바꿔 줄 수 있는지를 재귀로 확인하게 됩니다.

이분매칭에 대한 개념이 다 들어가있다고 생각하는데... 틀렸다고 나오네요..

도와주세요 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_2188 
{
	static int[][] data; 
	static int[] oldIndex;
	static boolean[] isVisit;
	static int house;
	static int cow;
	static int result;
	public static boolean binaryMatching(int index)
	{
		if(isVisit[index]) return false;
		isVisit[index] = true;
		
		for(int i = 1 ; i <= house ; i++ )
		{
			if(data[index][i] == 1)
			{
				if(oldIndex[i] == 0 || binaryMatching( oldIndex[i]) )	// 혹시 사람이 있으면 비켜줄 수 있냐고 물어보는 작업.
				{
					oldIndex[i] = index;		// 그 위치에 지금 들어간 사람을 index로 저장.
					return true;
				}
			}
		}
		return false;		// 못바꿔줌...
	}
	
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine(), " ");
		house = Integer.parseInt(token.nextToken());
		cow = Integer.parseInt(token.nextToken());
		data = new int[cow+1][house+1];
		oldIndex = new int[house+1];
		isVisit = new boolean[house+1];
		
		for(int i = 1 ; i <= cow ; i++)
		{
			token = new StringTokenizer(br.readLine(), " ");
			int count = Integer.parseInt(token.nextToken());
			
			for(int j = 0 ; j < count ; j++)
			{
				int row = Integer.parseInt(token.nextToken());
				data[i][row] = 1;
			}
		}
		
		for(int i = 1 ; i <= cow ; i++)
		{
			Arrays.fill(isVisit, false);
			if (binaryMatching(i))
			{
				result++;
			}
		}
		System.out.println(result);
	}
}

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

문제

문제

출처

ICPC

축사배정문제 왜 틀린지 모르겠습니다. 도와주세요

qhy0806 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말