문제풀이
- 방향 그래프를 구성한다.
- 보험이 가입되는 최대 자식 depth를 배열에 저장한다.
- 1부터 시작하는 dfs를 사용하여 현재 구성원이 보험에 가입이 되어있는지 여부를 판단한다.
주의사항
소요시간
25분
package AtCoder.ProblemList.Difficulty800_1199.FamilyandInsurance
fun main() {
val (N, M) = readln().trim().split(" ").map(String::toInt)
val outLists = List(N + 1) { mutableListOf<Int>() }
val P = readln().trim().split(" ").map(String::toInt)
for (i in P.indices) {
outLists[P[i]].add(i + 2)
}
val Y = IntArray(N + 1) { -1 }
repeat(M) {
val (x, y) = readln().trim().split(" ").map(String::toInt)
Y[x] = maxOf(Y[x], y)
}
fun dfs(from: Int = 1, y: Int = Y[from]): Int {
var result = if (y >= 0) 1 else 0
for (to in outLists[from]) {
result += dfs(to, maxOf(y - 1, Y[to]))
}
return result
}
println(dfs())
}