백준 11437번
https://www.acmicpc.net/problem/11437
LCA 알고리즘 문제이다.
DFS/BFS를 통해서 각 노드의 깊이를 구한다.
공통 부모를 찾으려는 노드의 깊이를 똑같이 맞춰준다.
두 노드를 동시에 부모 노드로 올라가면서 조상을 찾는다.
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()