[백준 - 1587번] 이분 매칭 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디

입력

첫째 줄에 nA와 nB가 주어진다. 둘째 줄에는 A와 B에 끝점을 두고 있는 간선의 개수 M이 주어진다. 다음 M개의 줄에는 간선의 정보가 i j와 같은 형식으로 주어지며, i는 집합 A의 정점 Ai, j는 B의 정점 (Bj)를 의미한다.

출력

첫째 줄에 입력으로 주어진 거의 이분 그래프의 최대 매칭의 수를 출력한다.

제한

• 1 ≤ nA, nB ≤ 1,000
• 0 ≤ M ≤ 50
• 1 ≤ Ai ≤ nA
• 1 ≤ Bj ≤ nB

풀이

이 문제는 이해하는 데 오래걸렸고, 솔루션은 금방 찾았다.

일단 풀이를 보기전에, 문제를 완벽히 이해하고 오길 바란다.

우리가 구해야 할 것은 최대 매칭 개수다.

만약, A와 B 집합의 개수 중 하나라도 짝수라면, 답은 nA/2 + nB/2가 된다.
예를 들어 설명해 보겠다.

A의 개수가 짝수라면 Ai - Ai+1 간선은 전부 가져갈 수 있으며, nB가 홀수라고 해도, 남은 하나를 처리해줄 정점이 없다. 그래서 nA/2 + nB/2가 된다.

두 집합의 개수가 전부 짝수라면, Ai - Ai+1, Bi - Bi+1 간선을 모두 가져갈 수 있기 때문에 이 경우도 nA/2 + nB/2가 최적해가 된다.

그러면 A, B 개수 모두 홀수인 경우는 어떨까? 이 경우는 두 집합에서 하나에 정점씩 남기 때문에 이를 간선으로 가져갈 수 있다면, 최적해가 된다.

그런데 중요한 것은 각 집합의 정점을 끝으로 하는 아무 간선을 가져가면 안된다.
예를 들어 이러한 경우가 있다.
A = {1, 2, 3}
B = {1, 2, 3, 4, 5}
M = 2
2 4 (A에서 2, B에서 4)
1 3

여기서 2 4를 가져간다면 어떻게 될까? 일단 두 집합의 개수는 짝수가 되긴 한다. 그렇지만
A는 1 o 3,
B는 1 2 3 o 5
이 되어서, 집합 내에서 연결된 간선을 모두 가져갈 수 없게 된다.

그러면, 1 3인 경우는 어떨까?
A는 2 3
B는 1 2 o 4 5
이 되어서 집햅 내에서 연결된 간선을 모두 가져갈 수 있게 된다. (2-3, 1-2, 4-5와 같이)

그래서 이를 일반화 한다면,
A, B 집합의 개수가 둘 다 홀수라면 M개의 간선 중 양 끝 정점이 각 집합에서 양 쪽을 짝수로 분할한다면, answer에 +1을 포함하고, nA/2 + nB/2를 더해주면 그 값이 최적해가 된다.

그리디 풀이는 O(M)이다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int nA, nB;
    static int M;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      nA = Integer.parseInt(st.nextToken());
      nB = Integer.parseInt(st.nextToken());
      
      M = Integer.parseInt(br.readLine());
      int finalA = nA;
      int finalB = nB;
      int answer = 0;
      if(nA % 2 == 1 && nB % 2 == 1) {
          for(int i=0; i<M; i++) {
              StringTokenizer st2 = new StringTokenizer(br.readLine());
              int a = Integer.parseInt(st2.nextToken());
              int b = Integer.parseInt(st2.nextToken());
              
              if(divisionEven(a, nA) && divisionEven(b, nB)) {
                  answer += 1;
                  break;
              }
          }
      }
      answer += finalA/2 + finalB/2;
      System.out.println(answer);
  }
  
  static boolean divisionEven(int v, int end) {
      if((v - 1) % 2 == 0 && (end - v) % 2 == 0) {
          return true;
      }
      return false;
  }
}