백준 2188번 - 축사배정

https://www.acmicpc.net/problem/2188

2188번: 축사 배정

[풀이]

 

이분매칭의 기본적인 문제이다.

 

A : 소        B : 축사

 

로 설정해서 A-B 에 해당하는 모든 간선을 그린 후, A 노드가 B 노드에 1:1 매칭될 수 있는 최대 매칭 수를 구한다.

 

기본적으로 dfs 개념을 숙지하고 dfs를 이용해서 풀어야한다.

 

처음으로 풀어 본 이분매칭 문제.

 

 

[소스코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class bj2188 {    // 축사 배정
        static BufferedReader br;
        static BufferedWriter bw;
        static StringTokenizer st;
        static int n;
        static int m;
        static boolean[][] connect;
        static int[] matchA;
        static int[] matchB;
        
    public static void main(String[] args) throws IOException {
        br=new BufferedReader(new InputStreamReader(System.in));
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String str=br.readLine();
        st=new StringTokenizer(str);
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        connect=new boolean[n+1][m+1];
        matchA=new int[n+1];
        matchB=new int[m+1];
        for(int i=1;i<=n;i++) {
            str=br.readLine();
            st=new StringTokenizer(str);
            int numB=Integer.parseInt(st.nextToken());
            for(int j=0;j<numB;j++) {
                int atob=Integer.parseInt(st.nextToken());
                connect[i][atob]=true;
            }
        }
        int result=go();
        bw.write(""+result);
        bw.flush();
        br.close();
        bw.close();
    }
    public static int go() {
        int so=0;
        boolean[] visit;
        for(int a=1;a<=n;a++) {
            visit=new boolean[n+1];
            if(dfs(a,visit)) so++;
        }
        
        return so;
    }
    public static boolean dfs(int a, boolean[] visit) {
        if(visit[a]) return false;
        visit[a]=true;
        for(int b=1;b<=m;b++) {
            if(connect[a][b]) {
                if(matchB[b]==0||dfs(matchB[b],visit)) {
                    matchA[a]=b;
                    matchB[b]=a;
                    return true;
                }
            }
        }
        return false;
    }
}