[BOJ] 11376 열혈강호 2 - P4

문제풀이

1. 한 사람이 최대 2개의 일을 담당할 수 있으므로, 이분 매칭을 진행할 때 2번씩 수행한다.

---

주의사항

---

소요시간

4분

---

package 백준.Platinum.P4.p11376_열혈강호2

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 (i in 0 until N) {
        repeat(2) {
            if (dfs(i)) count++
            visited.fill(false)
        }
    }
    println(count)
}

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

---

문제링크

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