백준 11437번
https://www.acmicpc.net/problem/11437

문제

---

생각하기

---

• LCA 알고리즘 문제이다.

  • (Lawest Common Ancestor) 최소 공통 조상 알고리즘

• DFS/BFS를 통해서 각 노드의 깊이를 구한다.

• 공통 부모를 찾으려는 노드의 깊이를 똑같이 맞춰준다.

  • 깊이가 더 깊은 노드를 차이만큼 반복해서 맞춰준다.

• 두 노드를 동시에 부모 노드로 올라가면서 조상을 찾는다.

동작

결과

코드

---

Kotlin

DFS

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0

private lateinit var adjList: MutableList<MutableList<Int>>
private lateinit var depths: IntArray
private lateinit var parents: IntArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    DFS(1, 0, 0)
    for (i in 0 until M) {
        StringTokenizer(br.readLine()).run {
            sb.append(LCA(nextToken().toInt(), nextToken().toInt())).append('\n')
        }
    }

    return sb.toString()
} // End of solve()

private fun DFS(current: Int, parent: Int, depth: Int) {
    parents[current] = parent
    depths[current] = depth

    for (next in adjList[current]) {
        if (next == parent) continue
        DFS(next, current, depth + 1)
    }
}

private fun LCA(a: Int, b: Int): Int {
    var node1 = a
    var node2 = b

    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]
    }

    return node1
} // End of LCA()

private fun input() {
    N = br.readLine().toInt()

    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }
    depths = IntArray(N + 1)
    parents = IntArray(N + 1)

    repeat(N - 1) {
        StringTokenizer(br.readLine()).run {
            val u = nextToken().toInt()
            val v = nextToken().toInt()

            adjList[u].add(v)
            adjList[v].add(u)
        }
    }

    M = br.readLine().toInt()
} // End of input()

BFS

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0

private lateinit var adjList: MutableList<MutableList<Int>>
private lateinit var depths: IntArray
private lateinit var parents: IntArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    BFS(1)
    repeat(M) {
        StringTokenizer(br.readLine()).run {
            val a = nextToken().toInt()
            val b = nextToken().toInt()

            sb.append(LCA(a, b)).append('\n')
        }
    }

    return sb.toString()
} // End of solve()

private fun BFS(node: Int) {
    val que = LinkedList<Int>()
    que.offer(node)
    parents[node] = node
    depths[node] = 0

    while (que.isNotEmpty()) {
        val nowNode = que.poll()

        for (nextNode in adjList[nowNode]) {
            if (nextNode == parents[nowNode]) continue

            parents[nextNode] = nowNode
            depths[nextNode] = depths[nowNode] + 1
            que.offer(nextNode)
        }
    }
} // End of BFS()

private fun LCA(a: Int, b: Int): Int {
    var node1 = a
    var node2 = b

    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]
    }

    return node1
} // End of LCA()

private fun input() {
    N = br.readLine().toInt()

    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }
    depths = IntArray(N + 1)
    parents = IntArray(N + 1)

    repeat(N - 1) {
        StringTokenizer(br.readLine()).run {
            val u = nextToken().toInt()
            val v = nextToken().toInt()

            adjList[u].add(v)
            adjList[v].add(u)
        }
    }

    M = br.readLine().toInt()
} // End of input()