[백준 8012번] 한동이는 영업사원! (Python3)

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

def findparent(x,d):
  for i in range(l+1):
    if d&(1<<i):
      x = sparse[i][x]
  return x

def findcoparent(x,y,c):
  if not c:
    if parent[x]==parent[y]:
      return parent[x]
    return sparse[1][x]
  if sparse[c][x]==sparse[c][y]:
    return findcoparent(x,y,c-1)
  return findcoparent(sparse[c][x],sparse[c][y],c-1)

def LCA(x,y):
  dx,dy = depth[x],depth[y]
  if dx>dy:
    x = findparent(x,dx-dy)
  elif dx<dy:
    y = findparent(y,dy-dx)
  if x==y:
    return x
  return findcoparent(x,y,l)

N = int(input())

graph = [[] for i in range(N+1)]
for _ in range(N-1):
  a,b = map(int,input().split())
  graph[a].append(b); graph[b].append(a)

dq = deque([(1,1)])
parent = [0]*(N+1); depth = [0]*(N+1)
while dq:
  now,d = dq.popleft()
  depth[now] = d
  for next in graph[now]:
    if not depth[next]:
      parent[next] = now
      dq.append((next,d+1))

l = len(bin(d))-3
sparse = [parent] + [[0]*(N+1) for i in range(l)]
for i in range(1,l+1):
  for n in range(1,N+1):
    sparse[i][n] = sparse[i-1][sparse[i-1][n]]

result = 0; now = 1
for _ in range(int(input())):
  next = int(input())
  result += depth[now]+depth[next]-depth[LCA(now,next)]*2
  now = next
print(result)

간단한 LCA [백준 11438번] LCA 2 (Python3) (tistory.com) 응용문제

LCA 알고리즘을 알고 있다면 쉽게 해결할 수 있다.

 

풀이를 설명하면,

1. 현재 노드와 방문해야하는 노드 now와 next에 대해서 LCA(now,next)를 구한다.

2. result에 (now의 깊이-LCA의 깊이) + (next의 깊이 - LCA의 깊이)를 더한다.

3. 결과를 출력한다.

 

아주 간단한 문제이지만 지문의 번역이 모호하게 되어있어서 시간을 좀 날린 문제였다. 방문해야하는 순서를 고려하지 않고 모든 도시를 방문하는 최솟값을 구하는 문제라고 생각해서 MST 응용문제라고 생각했는데, 그냥 LCA하면 되는 문제였다. 원문에는 정확하게 순서대로 방문하라는 말이 적혀있다고 하는데, 이 문제에는 그렇지 않아 시간을 좀 낭비했다. (참고 https://www.acmicpc.net/board/view/107549)

 

 

오늘의 교훈) 문제를 정확하게 이해하자