BOJ - 1298 ) 노트북의 주인을 찾아서

 

---

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

1298번: 노트북의 주인을 찾아서

---

이분 매칭의경우 네트워크플로우에서 최대유량이 1인간선으로 이루어진 네트워크중 A/B집합 두개로

 

나뉘어서 최대유량을 구하는 문제이다.

 

하지만 에드몬드카프로 구현하기보다는 DFS를 활용하여, 앞선 매칭을 바꿀수있는지? 에대한 재귀함수를

 

정의한다.

 

이해가 안되면 아래 강의를 추천한다. 

 

뭔가 이분매칭의경우, "두 집합간 최대한 매칭을 시킨다" 라는 느낌이 온다.

 

https://blog.naver.com/ndb796/221240613074

29. 이분 매칭(Bipartite Matching)

 

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {
  public static int m,n,result[];
  public static boolean check[];
  public static ArrayList<Integer> node[];
  public static void main(String[] args) throws Exception {
  
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    
    node = new ArrayList[n+1];
   
    result = new int[n+1];
    for(int i = 1 ; i <= n ; i++){node[i] = new ArrayList<>();}
    for(int i = 0 ; i < m ; i ++){
      st = new StringTokenizer(br.readLine());
      int s = Integer.parseInt(st.nextToken());
      int num = Integer.parseInt(st.nextToken());
      node[s].add(num);
    }

    int answer =0;
    for(int i = 1 ; i <= n ; i++){
      check = new boolean[n+1];
      if(bipartiteMatching(i)){
        answer++;
      } 
    }
    System.out.print(answer);
  }

  public static boolean bipartiteMatching(int x){
    
    for(int i = 0 ; i < node[x].size() ; i++){
      // 원하는 집
      int want = node[x].get(i);
      if(!check[want]){
        // 방문안했다면 방문처리 해주어 중복방지
        check[want] = true;
        if(result[want]==0 || bipartiteMatching(result[want])){
          result[want] = x;
          return true;
        }
      }
    }

    return false;
  }
}

---