1240: 노드사이의 거리

문제 링크

1240: 노드사이의 거리

구현 방식

• dfs 탐색하면서 구하고자하는 cost를 구해주면 된다
  • 재귀 종료조건: node == dest일 때 global_cost를 update 해주고 return
  • 중복 노드를 제거해주지 않으면 무한 재귀 호출을 할 수 있기 때문에 visit 1차원 list로 중복 노드를 제거해주었다

코드

import sys

N, M = map(int, sys.stdin.readline()[:-1].split())
edges = dict()
for n in range(N-1):
    a, b, cost = map(int, sys.stdin.readline()[:-1].split())
    if a in edges: edges[a].append((b, cost))
    else: edges[a] = [(b, cost)]
    if b in edges: edges[b].append((a, cost))
    else: edges[b] = [(a, cost)]

nodes = []
for m in range(M): nodes.append(list(map(int, sys.stdin.readline()[:-1].split())))

def dfs(node, dest, local_cost):
    global global_cost
    visit[node] = True
    if node == dest:
        global_cost = max(global_cost, local_cost)
        return
    for nnode, cost in edges[node]:
        if not visit[nnode]:
            dfs(nnode, dest, local_cost + cost)

for node in nodes:
    src, dest = node
    global_cost = 0
    visit = [False]*(N+1)
    dfs(src, dest, 0)
    print(global_cost)