만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 3176 도로 네트워크

23 Jun 2021

https://www.acmicpc.net/problem/3176

n개의 정점들로 이루어진 트리가 주어질 때 정점 쌍이 주어지면 두 정점을 연결하는 경로에서 가장 짧은 도로와 긴 도로의 길이를 출력하는 문제이다. 얼핏보면 세그먼트를 써야할 것도 같고 하지만 lca를 활용하는 문제이다.

먼저 lca에서 그동안은 공통 조상이 무엇인지 알아내는 문제를 주로 풀었다. 그런데 부모 정보 뿐만 아니라 값을 저장시켜 세그먼트 트리처럼 트리의 주어진 구간에서 원하는 값을 얻어낼 수도 있다.

var parent:[[(n:Int, minc: Int, maxc: Int)]] = []

만약 parent 배열을 위 처럼 정의한다고 하자. min cost와 max cost가 함께 정의된 형태이다.

func dfs(n: (Int, Int), p: Int) {
    depth[n.0] = depth[p] + 1
    check[n.0] = true
    parent[n.0][0] = (n: p, minc: n.1, maxc: n.1)
    for i in 1...maxK {
        let midParent = parent[n.0][i-1]
        let finalParent = parent[midParent.n][i-1]
        parent[n.0][i] = (n:finalParent.n, minc:min(midParent.minc, finalParent.minc), maxc:max(midParent.maxc, finalParent.maxc))
    }
    for e in edge[n.0] {
        if !check[e.0] {
            dfs(n: e, p: n.0)
        }
    }
}

그러면 기존의 lca처럼 부모 정보를 각 정점마다 저장시키기 위해 dfs를 돌려줄 것이다. 기존의 parent[n][i]의 의미는 n번 정점의 2i번째 부모였지만 이제는 부모가 무엇인지 뿐만아니라 n번 정점부터 2i번째 부모까지의 경로 중 거리의 최댓값과 최솟값을 같이 포함하고 있는 것이다.

3176

위의 그림을 보면 알 수 있듯이 주황색 즉 E의 22번째 부모를 구하려고한다. 그렇다면 우리는 dfs 구현에 의해 E의 21번째 부모로 가서 해당 정점의 21를 반환시켜줄 것이다. 그런데 자세히보면 E의 21번째 부모로 가는 도로의 최솟값과 최댓값을 이미 구해놨었고 C에서도 21번째 부모로의 최솟값과 최댓값을 이미 구해놨다. 따라서 E의 22부모로 가는 도로의 최솟값과 최댓값은 이 두 정보를 비교하기만 하면 되는 것이다.

이제 우리는 부모의 정보에 해당 부모까지 가는 도로의 최솟값과 최댓값을 알고있기 때문에 lca 알고리즘을 돌리는 과정에서 정점을 부모로 옮기는 순간마다 최솟값과 최댓값을 불러 비교해주기만 하면 된다.


var edge:[[(Int, Int)]] = []
var check:[Bool] = []
var depth:[Int] = []
var parent:[[(n:Int, minc: Int, maxc: Int)]] = []
let maxK = 18

func dfs(n: (Int, Int), p: Int) {
    depth[n.0] = depth[p] + 1
    check[n.0] = true
    parent[n.0][0] = (n: p, minc: n.1, maxc: n.1)
    for i in 1...maxK {
        let midParent = parent[n.0][i-1]
        let finalParent = parent[midParent.n][i-1]
        parent[n.0][i] = (n:finalParent.n, minc:min(midParent.minc, finalParent.minc), maxc:max(midParent.maxc, finalParent.maxc))
    }
    for e in edge[n.0] {
        if !check[e.0] {
            dfs(n: e, p: n.0)
        }
    }
}

func LCA(x: Int, y: Int) -> (Int, Int) {
    var a = x, b = y
    var maximum = 0, minimum = 1_000_001
    if depth[a] > depth[b] {
        swap(&a, &b)
    }
    for i in 0...maxK {
        let current = parent[b][maxK-i]
        if depth[a] <= depth[current.n] {
            maximum = max(maximum, current.maxc)
            minimum = min(minimum, current.minc)
            b = current.n
        }
    }
    if a == b {
        return (minimum, maximum)
    }
    for i in 0...maxK {
        let currentA = parent[a][maxK-i]
        let currentB = parent[b][maxK-i]
        if currentA.n != currentB.n {
            maximum = max(maximum, currentA.maxc, currentB.maxc)
            minimum = min(minimum, currentA.minc, currentB.minc)
            a = currentA.n
            b = currentB.n
        }
    }
    let LCANodeA = parent[a][0], LCANodeB = parent[b][0]
    maximum = max(maximum, LCANodeA.maxc, LCANodeB.maxc)
    minimum = min(minimum, LCANodeA.minc, LCANodeB.minc)
    return (minimum, maximum)
}

let n = Int(readLine()!)!
edge = Array(repeating: [], count: n+1)
check = Array(repeating: false, count: n+1)
depth = Array(repeating: 0, count: n+1)
parent = Array(repeating: Array(repeating: (n:0, minc: 0, maxc: 0), count: maxK+1), count: n+1)
for _ in 0..<n-1 {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    let A = line[0], B = line[1], C = line[2]
    edge[A].append((B, C))
    edge[B].append((A, C))
}
dfs(n: (1, 0), p: 0)
let m = Int(readLine()!)!
var str = ""
for _ in 0..<m {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    let result = LCA(x: line[0], y: line[1])
    str += "\(result.0) \(result.1)\n"
}
print(str)

Related posts