[백준 - 11437] LCA

문제링크

• dfs를 통해 각 node의 depth를 계산합니다.
• LCA를 구할 두 node의 depth를 동일하게 만듭니다.
• 두 node의 parent가 같아질 때까지 두 node의 parent를 비교합니다.

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<Int>

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) { 0 }
    dfs(1, 0)

    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] = root
            dfs(node, depth + 1)
        }
    }
}

fun printLCA(_node1: Int, _node2: Int) {
    var node1 = _node1
    var node2 = _node2
    while (depths[node1] != depths[node2]) {
        if (depths[node1] > depths[node2]) {
            node1 = parents[node1]
        } else {
            node2 = parents[node2]
        }
    }

    while (node1 != node2) {
        node1 = parents[node1]
        node2 = parents[node2]
    }
    bufferedWriter.write("$node1\n")
}

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

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