[BOJ - BFS] 1240번 : 노드 사이의 거리 ( python )

백준-  1240번 노드사이의거리 (골드5) BFS 문제이다.

 

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

1240번: 노드사이의 거리

 

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

 

 

---

 

맨날 기본 BFS/DFS 문제만 풀었었는데 간선에 대한 정보가 없는 것들이었다. 

 

그래서 이번엔 다익스트라와 플로이드 워셜에 들어가기전에!

BFS DFS로 간선 문제를 풀어보고 익숙해져야겠다고 생각이 들었다. 

 

 

1. 사고하기

• 목표 :  두 노드 사이의 거리 출력
• 유형 : bfs

간단하게 그래프를 만들어줄 때 간선도 같이 정보를 입력해주고, 잘 뽑아와서 사용하면 되는 문제라고 생각했다. 

간선정보를 같이 입력하는건 처음이어서 다른 분들의 코드를 잠시 참고했는데 생각한대로 적으면 됐었다!

 

 

가 . 입력과 그래프 생성

- graph를 노드 개수 +1 만큼 생성 ( 노드는 1~ n까지인데, 리스트는 0번부터시작하므로 n+1만큼 생성했다)

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

- 찾고자하는 두 노드를 입력받고 bfs() 함수에 두 노드번호를 매개변수로서 전달해 return 받은 노드사이의 거리를 출력했다.

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    n1, n2, l = map(int,input().split())
    graph[n1].append((n2,l))
    graph[n2].append((n1,l))

for _ in range(m):
    n1, n2 = map(int,input().split())
    print(bfs(n1,n2))

 

나.  bfs로 두 노드 사이의 거리를 return 하자

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

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

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

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

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

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

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

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

def bfs(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 graph[v]: #연관된 노드에 대한 노드번호와 간선길이
            if not visited[i]:
                visited[i] = True
                queue.append((i,d+l)) #지금까지 노드를 찾으면서 거리를 기록

 

 

---

2. 이 문제를 공유한 이유 >> 어서와 간선은 처음이지

 

그래프에 간선에 대한 정보를 추가할 때 간단하게 튜플로 묶어서 추가하면 된다는 사실을 알았다!

다른 분들도 거리 정보가 추가된 문제를 풀고 싶다면 이 문제부터 풀어보는 것을 추천한다. 

 

---

 

정답 코드

 

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

def bfs(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 graph[v]: #연관된 노드에 대한 노드번호와 간선길이
            if not visited[i]:
                visited[i] = True
                queue.append((i,d+l)) #지금까지 노드를 찾으면서 거리를 기록
    
n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    n1, n2, l = map(int,input().split())
    graph[n1].append((n2,l))
    graph[n2].append((n1,l))

for _ in range(m):
    n1, n2 = map(int,input().split())
    print(bfs(n1,n2))