[백준 - 11438] LCA2

문제링크

• 11437-LCA 풀이와 비슷하지만, 공통 부모를 찾는 과정에 차이점이 있습니다.
• node의 2^0, 2^1, ... 번째 parent를 저장합니다.
• 항상 node2의 깊이가 더 깊다고 가정하고, 두 node의 깊이 차이를 통해 node2를 node1과 같은 깊이에 위치하도록 이동시킵니다.
• 두 node의 부모가 같다면 바로 LCA를 출력하고, 같지 않다면 두 node의 부모가 다른 경우에만 node를 이동시킵니다. 즉, LCA 바로 직전까지 이동시킵니다.

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

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: Array<Boolean>
private lateinit var depths: Array<Int>
private lateinit var parents: Array<Array<Int>>
private const val SQUARE = 18 //◀ 2^17 = 131,072 > 100,000

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

    val n = bufferedReader.readLine().toInt()
    graph = Array(n + 1) { mutableListOf<Int>() }
    repeat(n - 1) {
        val (node1, node2) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }
        graph[node1].add(node2)
        graph[node2].add(node1)
    }

    depths = Array(n + 1) { 0 }
    visited = Array(n + 1) { false }
    parents = Array(n + 1) { Array(SQUARE) { 0 } }
    dfs(1, 0)
    setParents(n)

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

    bufferedReader.close()
    bufferedWriter.close()
}

fun dfs(root: Int, depth: Int) {
    visited[root] = true
    depths[root] = depth
    for (node in graph[root]) {
        if (!visited[node]) {
            parents[node][0] = root //◀ 2^0번째 부모
            dfs(node, depth + 1)
        }
    }
}

fun setParents(n: Int) {
    for (square in 1 until SQUARE) {
        for (node in 1..n) {
            // node의 2^sqaure번째 부모는 node의 2^(sqaure-1)번째 부모 node의 2^(square-1)번째 부모입니다.
            parents[node][square] = parents[parents[node][square - 1]][square - 1]
        }
    }
}

fun printLCA(_node1: Int, _node2: Int) {
    var node1 = _node1
    var node2 = _node2

    if (depths[node1] > depths[node2]) {
        val temp = node2
        node2 = node1
        node1 = temp
    }

    for (square in SQUARE - 1 downTo 0) {
        // 이진수를 생각하면 쉽게 이해할 수 있습니다.
        // ex. depths[node2] - depths[node1] = 7 -> 2^2 -> 2^1 -> 2^0 이동
        if ((depths[node2] - depths[node1]) >= (1 shl square)) {
            node2 = parents[node2][square]
        }
    }

    if (node1 == node2) {
        bufferedWriter.write("$node1\n")
        return
    }

    for (square in SQUARE - 1 downTo 0) {
        // LCA 바로 직전까지 이동시킵니다.
        if (parents[node1][square] != parents[node2][square]) {
            node1 = parents[node1][square]
            node2 = parents[node2][square]
        }
    }
    bufferedWriter.write("${parents[node1][0]}\n")
}

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

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