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

문제

---

생각하기

---

• LCA 알고리즘 문제이다.

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

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

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

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

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

• 루트 노드의 번호가 무조건1 이라는 보장이 없으므로 루트 노드의 번호가 몇번인지 확인해야 한다.

• 인접리스트를 통해서 graph를 표현했다.

동작

코드

---

Kotlin

DFS

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

private var N = 0

private lateinit var adjustList: MutableList<MutableList<Int>>

private var isVisited = BooleanArray(10_001)
private var isParent = BooleanArray(10_001)
private var depths = IntArray(10_001)
private var parents = IntArray(10_001)

private var resultStart = 0
private var resultEnd = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()
    var st: StringTokenizer

    var T = br.readLine().toInt()
    while (T-- > 0) {
        N = br.readLine().toInt()
        init()

        for (i in 1 until N) {
            st = StringTokenizer(br.readLine())
            val start = st.nextToken().toInt() // 부모 노드
            val end = st.nextToken().toInt() // 자식 노드

            // 자식이 되지 않는 노드를 찾는 배열
            isParent[end] = true

            adjustList[start].add(end)
            adjustList[end].add(start)
        }

        var rootNode = 0
        for (i in 1 until N) {
            if (!isParent[i]) {
                rootNode = i
                break
            }
        }

        st = StringTokenizer(br.readLine())
        resultStart = st.nextToken().toInt()
        resultEnd = st.nextToken().toInt()

        DFS(rootNode, 0)

        sb.append(LCA(resultStart, resultEnd)).append('\n')

        // 사용했던 배열 전부 초기화
        clear()
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun DFS(vertex: Int, depth: Int) {
    isVisited[vertex] = true
    depths[vertex] = depth

    adjustList[vertex].forEach {
        if (!isVisited[it]) {
            parents[it] = vertex
            DFS(it, depth + 1)
        }
    }
} // End of DFS

private fun LCA(node1: Int, node2: Int): Int {
    var n1 = node1
    var n2 = node2

    while (depths[n1] != depths[n2]) {
        if (depths[n1] > depths[n2]) {
            n1 = parents[n1]
        } else {
            n2 = parents[n2]
        }
    }

    while (n1 != n2) {
        n1 = parents[n1]
        n2 = parents[n2]
    }

    return n1
} // End of LCA

private fun clear() {
    isVisited.fill(false)
    isParent.fill(false)
    parents.fill(0)
    depths.fill(0)
} // End of clear

private fun init() {
    adjustList = ArrayList()
    for (i in 0..N) {
        adjustList.add(ArrayList())
    }
} // End of init

BFS

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

private var N = 0

private lateinit var adjustList: MutableList<MutableList<Int>>

private var isVisited = BooleanArray(10_001)
private var isParent = BooleanArray(10_001)
private var depths = IntArray(10_001)
private var parents = IntArray(10_001)

private var resultStart = 0
private var resultEnd = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()
    var st: StringTokenizer

    var T = br.readLine().toInt()
    while (T-- > 0) {
        N = br.readLine().toInt()
        init()

        for (i in 1 until N) {
            st = StringTokenizer(br.readLine())
            val start = st.nextToken().toInt() // 부모 노드
            val end = st.nextToken().toInt() // 자식 노드

            // 자식이 되지 않는 노드를 찾는 배열
            isParent[end] = true

            adjustList[start].add(end)
            adjustList[end].add(start)
        }

        var rootNode = 0
        for (i in 1 until N) {
            if (!isParent[i]) {
                rootNode = i
                break
            }
        }

        st = StringTokenizer(br.readLine())
        resultStart = st.nextToken().toInt()
        resultEnd = st.nextToken().toInt()

        BFS(rootNode, 0)
        sb.append(LCA(resultStart, resultEnd)).append('\n')

        // 사용했던 배열 전부 초기화
        clear()
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun BFS(vertex: Int, depth: Int) {
    val que: Queue<Int> = LinkedList()
    que.offer(vertex)
    parents[vertex] = depth
    depths[vertex] = depth

    while (que.isNotEmpty()) {
        val pollNode = que.poll()
        isVisited[pollNode] = true

        for (i in 0 until adjustList[pollNode].size) {
            var child: Int = adjustList[pollNode][i]
            if (!isVisited[child]) {
                parents[child] = pollNode
                depths[child] = depths[pollNode] + 1
                que.offer(child)
            }
        }
    }
} // End of DFS

private fun LCA(node1: Int, node2: Int): Int {
    var n1 = node1
    var n2 = node2

    while (depths[n1] != depths[n2]) {
        if (depths[n1] > depths[n2]) {
            n1 = parents[n1]
        } else {
            n2 = parents[n2]
        }
    }

    while (n1 != n2) {
        n1 = parents[n1]
        n2 = parents[n2]
    }

    return n1
} // End of LCA

private fun clear() {
    isVisited.fill(false)
    isParent.fill(false)
    parents.fill(0)
    depths.fill(0)
} // End of clear

private fun init() {
    adjustList = ArrayList()
    for (i in 0..N) {
        adjustList.add(ArrayList())
    }
} // End of init