BaekJoon 3176번 : 도로 네트워크 (python)

📝 BaekJoon 3176번 : 도로 네트워크 (P4 37.678%)

---

🔎 도로 네트워크 문제

---

📌 아이디어

Binary Lifting, LCA 알고리즘에서 가중치가 추가된 문제이다.

---

💭 풀이

• 이전에 풀었던 LCA알고리즘을 그대로 구현함과 동시에 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하기 위해 min_cost와 max_cost도 LCA알고리즘을 이용하여 업데이트 해준다.
• 해당 배열들은 j의 2^i의 조상 부모 노드까지의 경로에서 max_cost와 min_cost를 담고 있게 된다.
• 두 노드의 공통 조상 부모 노드를 찾을 때 table값과 동시에 max_cost와 min_cost값도 가져오며 해당 값의 가중치를 small과 big과 비교하여 업데이트 하며 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구할 수 있다.
• max_cost와 min_cost를 업데이트 하는 과정에서만 주의하면 쉽게 구현할 수 있는 알고리즘이다.

---

💻 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())

edge = [[] for _ in range(n+1)]
for _ in range(n-1) :
    a, b, c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))

level = [0]*(n+1)
root = [0]*(n+1)
table = [[0]*21 for _ in range(n+1)]
min_cost = [[float('inf')]*21 for _ in range(n+1)]
max_cost = [[0]*21 for _ in range(n+1)]

q = deque()
q.append((1,0))
check = [False]*(n+1)
check[1] = True
while q :
    x, count = q.popleft()
    level[x] = count

    for i in edge[x] :
        if not check[i[0]] :
            check[i[0]] = True
            root[i[0]] = (x, i[1])
            q.append((i[0],count+1))

for i in range(2,n+1) :
    table[i][0] = root[i][0]
    max_cost[i][0] = root[i][1]
    min_cost[i][0] = root[i][1]


for i in range(1, 21) :
    for j in range(1, n+1) :
        if table[j][i-1] != 0 :
            table[j][i] = table[table[j][i-1]][i-1]
            max_cost[j][i] = max(max_cost[j][i-1], max_cost[table[j][i-1]][i-1])
            min_cost[j][i] = min(min_cost[j][i-1], min_cost[table[j][i-1]][i-1])

m = int(input())
for _ in range(m) :
    a, b = map(int,input().split())
    small, big = float('inf'), 0
    if level[a] > level[b] :
        a, b = b, a
    
    for i in range(0,21) :
        if (level[b] - level[a]) & (1<<i) :
            big = max(big,max_cost[b][i])
            small = min(small,min_cost[b][i])
            b = table[b][i]
    
    if a == b :
        print(small, big)
    
    else :
        for i in range(0,21) :
            if table[b][i] != table[a][i] :
                big = max(big,max_cost[b][i], max_cost[a][i])
                small = min(small,min_cost[b][i], min_cost[a][i])
                a = table[a][i]
                b = table[b][i]

        small = min(small, root[a][1], root[b][1])
        big = max(big, root[a][1],root[b][1])
        print(small,big)

---