[BOJ] 11375 열혈강호 - P4

문제풀이

1. 이분 매칭을 이용하여 최대 매칭 횟수 구하기

---

주의사항

---

소요시간

5분

---

package 백준.Platinum.P4.p11375_열혈강호

const val EMPTY = -1
fun main() {
    val (N, M) = readln().split(" ").map(String::toInt)
    val matrix = Array(N) { readln().split(" ").map(String::toInt) }
    val idArr = IntArray(M + 1) { EMPTY }
    val visited = BooleanArray(M + 1)
    fun dfs(id: Int): Boolean {
        for (i in 1 until matrix[id].size) {
            val job = matrix[id][i]
            if (visited[job]) continue
            visited[job] = true
            if (idArr[job] == EMPTY || dfs(idArr[job])) {
                idArr[job] = id
                return true
            }
        }
        return false
    }

    var count = 0
    for (id in 0 until N) {
        if (dfs(id)) count++
        visited.fill(false)
    }
    println(count)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P4/p11375_%EC%97%B4%ED%98%88%EA%B0%95%ED%98%B8/p11375_%EC%97%B4%ED%98%88%EA%B0%95%ED%98%B8.kt

---

문제링크

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

---

회고

이분 매칭에 대해 학습할 수 있었다.