[BOJ] Q3176 도로 네트워크

[BOJ] Q3176 도로 네트워크

Question

Language: Python

Difficulty: Platinum 4

해당 문제는 11437의 연장선상에 있는 문제로 LCA를 응용하여 풀이하는 문제이다. LCA에서는 부모값만 저장하였지만, 해당 문제에서는 부모값과 최소 기리의 도로, 최대 길이의 도로값을 저장하는 부분을 추가한다.

min/max weight 초기화 과정

vertex 와 parent 간의 희소 배열을 초기화하는 과정으로 아래와 같은 방식으로 초기화를 진행한다.

vertex -> parent of parent로 가는 min/max weight를 구하기 위해 vertex -> parent 와 parent -> parent of parent의 min/max weight을 활용한다.

for i in range(1,length):
    for j in range(1,n+1):
        near_parent=parents[j][i-1]
        parents[j][i]=parents[near_parent][i-1]
        #vertex -> parent 까지의 min/max weight와 parent -> parent of parent의 min/max weight을 비교해서 vertex -> parent of parent 값을 초기화한다.
        values=[min_max[j][i-1][0],min_max[j][i-1][1],min_max[near_parent][i-1][0],min_max[near_parent][i-1][1]]
        min_max[j][i]=[min(values),max(values)]

Solution

from math import inf
from collections import deque
def solution():
    length=21
    parents=[[0] * length for _ in range(n+1)]
    min_max=[[[inf,-inf] for _ in range(length)] for _ in range(n+1)]

    queue=deque([1])
    visited=[False]*(n+1)
    levels=[0]*(n+1)
    visited[1]=True

    while queue:
        vertex=queue.popleft()

        for adj_vertex,weight in graph[vertex]:
            if visited[adj_vertex]:
                continue
            visited[adj_vertex]=True
            levels[adj_vertex]=levels[vertex]+1
            parents[adj_vertex][0]=vertex
            min_max[adj_vertex][0]=[weight,weight]
            queue.append(adj_vertex)

    for i in range(1,length):
        for j in range(1,n+1):
            near_parent=parents[j][i-1]
            parents[j][i]=parents[near_parent][i-1]
            #vertex -> parent 까지의 min/max weight와 parent -> parent of parent의 min/max weight을 비교해서 vertex -> parent of parent 값을 초기화한다.
            values=[min_max[j][i-1][0],min_max[j][i-1][1],min_max[near_parent][i-1][0],min_max[near_parent][i-1][1]]
            min_max[j][i]=[min(values),max(values)]

    for v1,v2 in queries:
        v1,v2=(v1,v2) if levels[v1]<levels[v2] else (v2,v1)
        min_weight,max_weight=inf,-inf
        #높이 맞춰주기
        for i in range(length-1,-1,-1):
            if levels[v2]-levels[v1] >=2**i:
                min_weight=min(min_weight,min_max[v2][i][0])
                max_weight=max(max_weight,min_max[v2][i][1])
                v2=parents[v2][i]
        if v1==v2:
            print(min_weight,max_weight)
            continue
        #같은 높이에서 공통 부모를 찾아가는 과정
        for i in range(length-1,-1,-1):
            if parents[v1][i] != parents[v2][i]:
                min_weight=min(min_weight,min_max[v1][i][0],min_max[v2][i][0])
                max_weight=max(max_weight,min_max[v1][i][1],min_max[v2][i][1])

                v1=parents[v1][i]
                v2=parents[v2][i]

        min_weight=min(min_weight,min_max[v1][0][0],min_max[v2][0][0])
        max_weight=max(max_weight,min_max[v1][0][1],min_max[v2][0][1])
        print(min_weight,max_weight)
        

if __name__ == "__main__":
    n=int(input())
    graph=[[] for _ in range(n+1)]

    for _ in range(n-1):
        v1,v2,weight=map(int,input().split())
        graph[v1].append((v2,weight))
        graph[v2].append((v1,weight))
        
    m=int(input())
    queries=[list(map(int,input().split())) for _ in range(m)]

    solution()