[백준_1240] 노드사이의거리 python

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

1240번: 노드사이의 거리

문제해결

• 양방향 연결노드에 대한 정보가 주어지고 노드 a에서 b까지의 거리를 구하는 문제
• 방문처리는 1차원 배열로 가능하지만 a~b 까지 도달하는 각 거리를 저장하기 위해서 graph는 2차원으로 처리하였다.
• 완전탐색으로 dfs, bfs 둘중 한방법을 선택해도 되지만, 한 점에서 목표지점까지를 방문함에 있어서 거리를 파라미터로 넘기고싶어 dfs로 처리하였다.
•  

import sys
def input():
    return sys.stdin.readline().rstrip()
n,m = map(int,input().split())
graph =[[0]*(n+1) for _ in range(n+1)]
answer = 0
def dfs(s,e,dist):
    global answer
    visited[s] = 1
    # for nx in graph[s]:
    for i in range(1,n+1):
        dis = graph[s][i]#거린데
        if graph[s][i]>0 and not visited[i]:
            if i == e:
                answer = dist+graph[s][i]
            else:
                dfs(i,e,dist+graph[s][i])

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

for _ in range(m):
    visited = [0]*(n+1)
    a,b = map(int,input().split())
    dfs(a,b,0)
    print(answer)