일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 백준
- MYSQL
- programmers
- 파이썬
- 백준알고리즘
- 소프티어
- 회고
- 코딩봉사
- 코틀린
- SQL
- python
- C++
- 스프링
- 문제풀이
- SW봉사
- 1과목
- 시나공
- 공부일지
- kotlin
- 프로그래머스
- 코딩교육봉사
- 알고리즘
- 자바
- 정보처리산업기사
- BFS
- 백준 알고리즘
- 데이터베이스
- java
- CJ UNIT
- softeer
- Today
- Total
JIE0025
[BOJ - BFS] 1240번 : 노드 사이의 거리 ( python ) 본문
백준- 1240번 노드사이의거리 (골드5) BFS 문제이다.
https://www.acmicpc.net/problem/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))
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ - DP] 14916번 : 거스름돈 ( python ) (0) | 2022.04.12 |
---|---|
[BOJ - 이분탐색] 16564번 : 히오스 프로그래머 ( python ) (0) | 2022.04.08 |
[BOJ - BFS] 7562번 : 나이트의 이동 ( python ) (0) | 2022.04.05 |
[BOJ - DFS] 1068번 : 트리 ( python ) (0) | 2022.04.04 |
[BOJ - 이분탐색] 14627번 : 파닭파닭 ( python ) (0) | 2022.04.03 |