[백준 파이썬] 1240 노드 사이의 거리

 

1240번: 노드사이의 거리

 

 

문제

노드의 정보를 입력받고 노드 사이의 거리를 구하는 문제이다.

 

---

 

풀이

노드의 거리가 주어지고 특정 노드 사이의 거리를 구하는 문제이므로 깊이 우선탐색으로 해결하였다.

 

 

N, M = map(int, input().split())
graph = list([0] * (N + 1) for _ in range(N + 1))

노드와 그 노드의 거리를 입력받아야 하므로 2차원 배열을 생성해 입력받아 주었다.

 

def dfs(s, e, dist):
  global answer
  visited[s] = 1
  for i in range(1, N + 1):
    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])

 

dfs는 위와같이 구현하였다.

먼저 해당 노드를 방문했다는 표시를 visited값으로 입력하였고, 해당 노드에 입력되어있는 다른 노드와의 거리를 모두 체크한다. 이 때 거리가 0인 노드는 넘어가고 거리가 0이아닌 노드 중 end값에 도달했으면 현재까지의 거리 (dist)값과 해당 노드의 거리를 더하여 answer값에 입력해준다.

만약 end에 도달하지 않았으면 해당 노드를 다시 dfs넣어 깊이 우선탐색을 진행한다.

---

코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = list([0] * (N + 1) for _ in range(N + 1))
answer = 0

def dfs(s, e, dist):
  global answer
  visited[s] = 1
  for i in range(1, N + 1):
    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 i in range(N-1):
  a, b, c = map(int, input().split())
  graph[a][b] = c
  graph[b][a] = c

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