백준 1240 노드사이의 거리 / python

문제 : 1240

풀이 point

입력 받은 데이터를 통해 인접리스트를 만든다.

트리이기 때문에 순환 관계가 없으므로 dfs를 활용하여 두 노드간의 길이를 계산한다.

풀이 방법

재귀를 활용하였는데, 이때 result가 None이라면 더이상 이어진 노드가 없는 것이므로 값을 버리고, 만약 None이 아니라면 현재 노드까지의 길이가 저장되어있기 때문에 그 값을 return 하도록 하여 재귀를 이어나간다. 최종적으로 목표 노드까지 도달했다면 그동안 저장되어왔던 s를 return한다.

풀이 코드

def dfs(visit, node, target, s):
  if node == target:
    return s
  
  for n, dist in tree[node]:
    if visit[n]:
      continue
    visit[n] = True
    result = dfs(visit, n, target, s+dist)
    if result is not None:
      return result

N, M = map(int, input().split())

tree = [[] for _ in range(N+1)]

for _ in range(N-1):
  a, b, d = map(int, input().split())
  tree[a].append((b, d))
  tree[b].append((a, d))

for _ in range(M):
  a, b = map(int, input().split())
  visit = [False]*(N+1)
  visit[a] = True
  print(dfs(visit, a, b, 0))