BOJ 1240 - 노드사이의 거리

문제

백준 온라인 저지 - 1240번

풀이 과정

트리 는 특정 정점에서 다른 정점까지 단 하나의 경로가 존재합니다.
따라서 BFS 를 이용해 각 정점까지의 거리를 구할 수 있습니다.
이때 인접 리스트를 이용해서 그래프를 구현한다면 O(V+E) 의 시간 복잡도로 문제를 해결할 수 있습니다.

코드

import sys
from collections import deque


def make_graph(edges):
    graph = {n + 1: [] for n in range(N)}

    for frm, to, cost in edges:
        graph[frm].append([to, cost])
        graph[to].append([frm, cost])

    return graph


def bfs(start, goal):
    q = deque()
    visit = [0] * (N + 1)

    q.append([start, 0])
    visit[start] = 1

    while q:
        here, acc_cost = q.popleft()
        if here == goal:
            return acc_cost

        for there, cost in graph[here]:
            if not visit[there]:
                visit[there] = 1
                q.append([there, cost + acc_cost])


def solution(frm, to):
    return bfs(frm, to)


if __name__ == '__main__':
    N, M = list(map(int, sys.stdin.readline().split()))
    edges = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
    pairs = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

    graph = make_graph(edges)

    for frm, to in pairs:
        answer = solution(frm, to)
        print(answer)