[백준 - 3584] 가장 가까운 공통 조상

문제링크

• LCA2 문제풀이를 참고해주세요.

import java.io.BufferedReader
import java.io.BufferedWriter

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var tree: Array<MutableList<Int>>
private lateinit var isRoot: Array<Boolean>
private lateinit var depths: Array<Int>
private lateinit var parents: Array<Array<Int>>
private const val SQUARE = 15 //◀ 2^14 = 16,384 > 10,000

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    val t = bufferedReader.readLine().toInt()
    repeat(t) {
        val n = bufferedReader.readLine().toInt()
        tree = Array(n + 1) { mutableListOf() }
        isRoot = Array(n + 1) { true }
        depths = Array(n + 1) { 0 }
        parents = Array(n + 1) { Array(SQUARE) { 0 } }

        repeat(n - 1) {
            val (parent, child) = bufferedReader
                .readLine()
                .split(" ")
                .map { it.toInt() }
            tree[parent].add(child)
            isRoot[child] = false
        }

        for (node in 1..n) {
            if (isRoot[node]) {
                dfs(node, 0)
            }
        }
        setParents(n)

        val (node1, node2) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }

        val answer = lca(node1, node2)
        bufferedWriter.write("$answer\n")
    }

    bufferedReader.close()
    bufferedWriter.close()
}

fun dfs(root: Int, depth: Int) {
    depths[root] = depth

    for (node in tree[root]) {
        parents[node][0] = root
        dfs(node, depth + 1)
    }
}

fun setParents(n: Int) {
    for (square in 1 until SQUARE) {
        for (node in 1..n) {
            parents[node][square] = parents[parents[node][square - 1]][square - 1]
        }
    }
}

fun lca(_node1: Int, _node2: Int): Int {
    var node1 = _node1
    var node2 = _node2
    if (depths[node1] > depths[node2]) {
        val temp = node1
        node1 = node2
        node2 = temp
    }

    for (square in SQUARE - 1 downTo 0) {
        if ((depths[node2] - depths[node1]) >= (1 shl square)) {
            node2 = parents[node2][square]
        }
    }

    if (node1 == node2) return node1

    for (square in SQUARE - 1 downTo 0) {
        if (parents[node1][square] != parents[node2][square]) {
            node1 = parents[node1][square]
            node2 = parents[node2][square]
        }
    }
    return parents[node1][0]
}

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.