백준 1240 : 노드사이의 거리 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(start,end , check):

    global count

    if start==end:
        count=check
        return

    for i,j in Tree[start]:
        if not visit[i]:
            visit[i]=True
            DFS(i, end , check+j)

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

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

for i in range(N-1):
    a,b,c=map(int,input().split())
    Tree[a].append([b,c])
    Tree[b].append([a,c])

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

    DFS(a,b , 0)
    print(count)

📌 어떻게 접근할 것인가?

서로 연결된 정점과 간선의 가중치가 주어졌을때 두 정점의 거리를 구하는 문제입니다.
단순히 $DFS$ 를 통해 구현했습니다.

다만 $Tree$ 를 입력받을때 서로 연결된 정점뿐만 아니라 가중치도 함께 넣어주고
방문 체크를 해주면서 $M$ 개의 쿼리에서 $a,b$ 두 지점이 같아질때까지 계속 탐색을 해줍니다.

만약 start==end 이라면 count 변수에 거리를 저장해준후 출력해줍니다.

저는 $DFS$ 를 통해 구현을 했는데 $DFS$ 로도 구현이 가능합니다.