[백준 3176번] 도로 네트워크 (Python3)

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

def findparent(x,d):
  global minresult,maxresult
  for i in range(logd+1):
    if d&(1<<i):
      minresult = min(minresult,mincost[i][x])
      maxresult = max(maxresult,maxcost[i][x])
      x = sparse[i][x]
  return x

def findcoparent(x,y,c):
  global minresult,maxresult
  if c == 0:
    if parent[x] == parent[y]:
      minresult = min(minresult,mincost[0][x],mincost[0][y])
      maxresult = max(maxresult,maxcost[0][x],maxcost[0][y])
    else:
      minresult = min(minresult,mincost[1][x],mincost[1][y])
      maxresult = max(maxresult,maxcost[1][x],maxcost[1][y])
  elif sparse[c][x] == sparse[c][y]:
    findcoparent(x,y,c-1)
  else:
    minresult = min(minresult,mincost[c][x],mincost[c][y])
    maxresult = max(maxresult,maxcost[c][x],maxcost[c][y])
    findcoparent(sparse[c][x],sparse[c][y],c-1)

N = int(input())

graph = [[] for i in range(N)]
for _ in range(N-1):
  x,y,w = map(int,input().split())
  graph[x-1].append((y-1,w))
  graph[y-1].append((x-1,w))

parent = [0]*N
depth = [0]*N
cost = [0]*N

dq = deque([(0,1)])
while dq:
  now,d = dq.popleft()
  depth[now] = d
  for next,w in graph[now]:
    if depth[next]:
      continue
    parent[next] = now
    cost[next] = w
    dq.append((next,d+1))

cost1 = cost[:]
cost1[0] = 1e9

logd = int(log2(d-1))

sparse = [parent]+[[0]*N for i in range(logd)]
mincost = [cost1]+[[0]*N for i in range(logd)]
maxcost = [cost]+[[0]*N for i in range(logd)]
for i in range(1,logd+1):
  for n in range(N):
    sparse[i][n] = sparse[i-1][sparse[i-1][n]]
    mincost[i][n] = min(mincost[i-1][n],mincost[i-1][sparse[i-1][n]])
    maxcost[i][n] = max(maxcost[i-1][n],maxcost[i-1][sparse[i-1][n]])

K = int(input())
for _ in range(K):
  x,y = map(lambda x:x-1,map(int,input().split()))
  minresult,maxresult = 1e9,0
  if depth[x] > depth[y]:
    x = findparent(x,depth[x]-depth[y])
  elif depth[y] > depth[x]:
    y = findparent(y,depth[y]-depth[x])
  if x != y:
    c = int(log2(depth[x]-1))
    findcoparent(x,y,c)
  print(minresult,maxresult)

LCA2 [백준 11438번] LCA 2 (Python3) (tistory.com) 를 활용하는 문제.

 

LCA2를 풀었다면 풀이는 금방 떠올릴 수 있지만 구현하는게 약간 까다로웠다.

LCA 알고리즘이 아직 익숙지 않아서 그런 것 같기도 하고...

 

LCA 알고리즘을 알고 있다는 가정하에 풀이를 요약하면,

1. sparse table을 3개를 만든다. 이때 부모노드에 대한 sparse, 최소cost에 대한 sparse, 최대cost에 대한 sparse이다.

2. LCA로 두 노드의 공통조상을 찾아가는 과정에서 cost에 대한 sparse를 이용해서 최솟값과 최댓값을 갱신한다.

 

이때 1번과정에서 cost에 대한 sparse를 만들 때, 1-1의 경로는 존재하지 않으므로 무시하기 위해서 1번에서 1번노드의 cost를 최소 cost 에서는 1e9로, 최대 cost에서는 0으로 저장하는 것이 좋다.

 

 

오늘의 교훈) LCA와 sparse table을 적재적소에 활용할 수 있도록 익숙해지자