(Python) [BOJ 1240] 노드사이의 거리

(Python) [BOJ 1240] 노드사이의 거리

문제: https://www.acmicpc.net/problem/1240

N개의 노드로 구성된 트리에서 M개의 노드쌍 사이 거리를 출력하는 문제입니다.

BFS를 활용하여 해결하였습니다.

import sys from collections import deque def get_dist(start, end): # BFS # SETTING visited = [-1] * (N + 1) # 방문 확인과 동시에 거리 저장 visited[start] = 0 q = deque([start]) while q: n_now = q.popleft() if visited[end] != -1: return visited[end] for n_next, weight in graph[n_now]: if visited[n_next] == -1: visited[n_next] = visited[n_now] + weight q.append(n_next) # 1. INPUT N, M = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N+1)] # 무방향 for _ in range(N-1): n_start, n_end, weight = map(int, sys.stdin.readline().split()) graph[n_start].append((n_end, weight)) # 도착 노드, 가중치(거리) graph[n_end].append((n_start, weight)) targets = [list(map(int, sys.stdin.readline().split())) for _ in range(M)] # 2. BODY for n_start, n_end in targets: # 3. OUTPUT print(get_dist(n_start, n_end)) # 시작 노드, 도착 노드

from http://sangdanghyunjeo.tistory.com/3 by ccl(A) rewrite - 2021-12-13 14:00:58