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

1240번: 노드사이의 거리

from collections import deque

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]

for _ in range(n-1): # n-1개의 간선을 입력받고, 양방향으로 저장
    start, end, distance = map(int,input().split())
    graph[start].append((end,distance))
    graph[end].append((start,distance))

cases = [tuple(map(int,input().split())) for _ in range(m)] # 노드간의 거리를 찾고자 하는 노드쌍

def dfs(start,end,distance,visited): # 그래프 탐색을 위한 DFS 함수

    if start == end: # 최종 노드에 도착한 경우 누적된 거리를 출력하고 종료
        print(distance)
        return

    for next_node,value in graph[start]: # 다음 노드번호와 거리
        if not visited[next_node]: # 만약에 아직 방문하지 않았다면
            visited[next_node] = True
            dfs(next_node,end,distance+value,visited) # 방문처리와 동시에 탐색
            visited[next_node] = False

def bfs(start,end,distance): # 그래프 탐색을 위한 BFS 함수

    queue = deque([(start,distance)])
    visited = [False]*(n+1)

    visited[start] = True 

    while queue:
        current, summary = queue.popleft()

        if current == end: # 최종 노드에 도착한 경우 누적된 거리를 출력하고 종료
            print(summary)
            return

        for next_node,value in graph[current]: # 다음 노드번호와 거리
            if not visited[next_node]: # 만약에 아직 방문하지 않았다면
                visited[next_node] = True
                queue.append((next_node,summary + value)) # 방문처리와 동시에 탐색
    

for x, y in cases: # 노드간의 거리를 찾고자 하는 노드쌍을 DFS/BFS로 처리
    visited = [False]*(n+1)
    visited[x] = True
    # dfs(x,y,0,visited)
    bfs(x,y,0)

 

이번 문제는 N개의 노드와 N-1개의 간선으로 이루어진 트리에서 두 노드사이의 거리를 구하는 문제이다.

 

그래프를 탐색하기 위한 알고리즘인 DFS/BFS로 풀이하면 되는 문제이다. 인접 리스트 방식으로 그래프 정보를 저장하고, 최종 노드에 도달할 때까지 DFS/BFS로 탐색해주며 거리를 누적해주면 된다.(본인은 DFS로 먼저 풀이해본 뒤 BFS로도 풀이해보았다.)

 

DFS 알고리즘

def dfs(start,end,distance,visited): # 그래프 탐색을 위한 DFS 함수

    if start == end: # 최종 노드에 도착한 경우 누적된 거리를 출력하고 종료
        print(distance)
        return

    for next_node,value in graph[start]: # 다음 노드번호와 거리
        if not visited[next_node]: # 만약에 아직 방문하지 않았다면
            visited[next_node] = True
            dfs(next_node,end,distance+value,visited) # 방문처리와 동시에 탐색
            visited[next_node] = False

 

BFS 알고리즘

def bfs(start,end,distance): # 그래프 탐색을 위한 BFS 함수

    queue = deque([(start,distance)])
    visited = [False]*(n+1)

    visited[start] = True 

    while queue:
        current, summary = queue.popleft()

        if current == end: # 최종 노드에 도착한 경우 누적된 거리를 출력하고 종료
            print(summary)
            return

        for next_node,value in graph[current]: # 다음 노드번호와 거리
            if not visited[next_node]: # 만약에 아직 방문하지 않았다면
                visited[next_node] = True
                queue.append((next_node,summary + value)) # 방문처리와 동시에 탐색

 

 

👉🏻 BFS가 더 빠르게 동작하는 것으로 결과가 나왔다.