(BOJ) 1587 이분매칭

1587 이분매칭

• 분류 : 탐욕법

문제

그래프의 최대 매칭 (Maximum Matching)은 두 간선이 같은 정점을 공유하지 않는 간선의 최대 집합을 말한다.

이분 그래프 (Bipartited Graph)는 그래프의 모든 정점을 두 집합 A와 B로 나눌 수 있는 그래프이다.

모든 간선의 끝 점은 A에 하나, B에 하나 있어야 한다.

이분 그래프에서 최대 매칭을 구하는 문제는 Maximum Flow 알고리즘을 이용해서 풀 수 있다.

거의 이분 그래프는 모든 정점이 집합 A = {A1, A2, …, AnA}와 B = {B1, B2, …, BnB}로 나누어져 있고, 모든 간선의 끝 점은 A에 하나, B에 하나있는 그래프이다.

여기까지는 이분 그래프와 동일한 모양을 갖는다.

거의 이분 그래프는 이분 그래프와 다르게 nA-1 + nB-1개의 간선을 추가로 가진다.

추가가 되는 간선은 Ai에서 Ai+1로 가는 간선 (1 ≤ i ≤ nA-1)과 Bi에서 Bi+1로 가는 간선 (1 ≤ i ≤ nB-1)이다.

따라서, 끝 점이 A에 하나, B에 하나 있는 간선의 개수를 M이라고 했을 때, 정점의 수가 nA + nB인 거의 이분 그래프의 간선의 개수는 M + nA-1 + nB-1이 된다.

거의 이분 그래프의 정점의 개수를 나타내는 nA, nB와 A와 B에 끝점을 두고 있는 간선 M개가 입력으로 주어졌을 때, 최대 매칭을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 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

예제 입력 1

6 6
4
1 3
1 5
3 6
4 2

예제 출력 1

6

예제 입력 2

3 3
3
1 1
2 2
3 3

예제 출력 2

3

예제 입력 3

3 3
2
1 2
2 3

예제 출력 3

2

예제 입력 4

13 16
17
6 8
3 4
7 11
3 13
8 1
3 1
8 4
7 5
3 8
7 3
2 6
4 3
1 15
11 16
13 2
12 2
11 2

예제 출력 4

14

Solution

Expander

import java.util.*

private const val MAX = 1001

private var nA: Int = 0
private var nB: Int = 0
private var M: Int = 0

private var DP = Array(MAX) {
    IntArray(MAX) {
        0
    }
}


private var graph = Array(MAX) {
    BooleanArray(MAX) {
        false
    }
}


fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    nA = nextInt()
    nB = nextInt()
    M = nextInt()
    repeat(M) {
        val u = nextInt()
        val v = nextInt()
        graph[u][v] = true
    }
}


private fun solve() {
    var result = 0
    for (i in 0 .. nA) {
        for (j in 0 .. nB) {
            if (1 < i && 1 < j) {
                DP[i][j] = DP[i - 2][j - 2] + 2
            }
            if (1 < i) {
                DP[i][j] = Math.max(DP[i][j], DP[i - 2][j] + 1)
            }
            if (1 < j) {
                DP[i][j] = Math.max(DP[i][j], DP[i][j - 2] + 1)
            }
            if (graph[i][j]) {
                DP[i][j] = Math.max(DP[i][j], DP[i - 1][j - 1] + 1)
            }
            result = Math.max(result, DP[i][j])
        }
    }
    println(result)
}

Point of Thinking

• 이분 매칭의 정의에 따라 구현 후 최대 매칭 수를 구하는 문제이다.
• 각 간선들의 범위 내에서 순회하며 최대 유량 계산 알고리즘을 적용하면 바로 Accepted.

References

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