[알고리즘] 백준 - 1240 노드 사이의 거리

백준 1240문제

접근

- 두 노드 사이의 거리를 출력하기

- bfs 로 풀기

- 간선에 대한 정보를 추가할때 튜플로 묶어서 추가하면 된다

 

그래프 생성

- 리스트는 0부터 시작을 하므로, board에 n+1 개수만큼의 노드를 생성해준다.

- 두 노드 번호와 간선의 정보를 입력 받고, 그래프에 추가시 ( 노드 번호, 간선 길이) 형태로 추가

- bfs 함수에 두 노드번호를 매개변수로 전달해 return 받은 노드 사이의 거리 출력

 

두 노드 사이 구하는 함수 ( bfs() ) 

- 매개변수로 시작 노드와 찾는 노드 번호를 입력받는다.

- queue를 생성하고, 시작 노드와 거리는 0으로 초기화한다. 

- 여러번의 테스트케이스를 실행해야하므로 visited 변수는 bfs 안에 생성했다. 

- popleft 해서 현재 노드와 d를 가져오는데, d는 start 노드로부터 현재 노드 v까지의 거리를 의미한다. 

당연히 처음엔 start를 입력하고 바로 노드를 뺐으므로 d에는 0이 나온다. 

- 현재 노드 v가 찾고자하는 노드일 경우 d를 return 해준다. 

- 현재 노드 v와 연관된 노드를 가져온다. board에는 두개의 정보(노드번호, 연결 길이) 가 들어있으므로 for문에서 i와 l로 받아왔다. 

- 방문하지 않은 노드일 경우 방문처리해주고, queue에 (연관된 노드번호 i, 지금까지의거리) 를 설정해준다.

 

풀이

import sys
from collections import deque
input = sys.stdin.readline

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


def distance(start, find):
    queue = deque()
    queue.append((start, 0))

    visited = [False] * (n+1)
    visited[start] = True

    while queue:
        v, d = queue.popleft()
        if v == find:
            return d
        for i, l in board[v]:
            if visited[i] == False:
                visited[i] = True
                queue.append((i, d+l))


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

for _ in range(m):
    a, b = map(int, input().split())
    print(distance(a, b))