[백준/BOJ] - 1240번 python 풀이 - bfs

---

노드와 노드 사이의 거리를 저장해주어야 하는데 값 입력 받았을 때 어떤식으로 저장해야할지 고민해야하는 문제

 

bfs로 돌리면 함수의 매개변수가 최초 시작점, 도착 지점으로 고정되기 때문에 변수를 가져다 쓰기 용이

 

queue에 기준 노드와 연결되어있는 (노드, 거리)를 append 해준다.

 

append 할 때 누적 distance를 계산하여 넣어준다.

 

queue에서 꺼낸 노드와 도착지 노드가 동일할 경우 누적 distance를 출력

 

---

import sys
from collections import deque

def bfs(start, end):    
    q = deque()
    q.append((start,0)) #노드, 누적 거리
    
    ok = [False] * (n+1)
    ok[start] = True

    while q:
        nd, d = q.popleft()

        if nd == end: #최종 목적지와 큐에서 꺼낸 노드 값이 같으면
            return d #누적 거리 출력
        for i, j in arr[nd]: #노드, 거리            
            if not ok[i]:
                q.append((i,d+j))
                ok[i] = True


n, m = map(int,input().split())
arr = [[] for _ in range(n+1)]

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

for _ in range(m):
    s,e = map(int,input().split())
    print(bfs(s,e))