15591번: MooTube (Silver) (acmicpc.net)
15591번: MooTube (Silver)
농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의
www.acmicpc.net
문제

풀이
문제가 쓸데없이 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다.
따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해주면 된다.
코드
from collections import deque
def bfs(k, v):
queue = deque()
queue.append((v, 987_654_321))
isVisited = [False] * (n + 1)
isVisited[v] = True
answer = 0
while queue:
cur_node, cur_usado = queue.popleft()
for next_node, next_usado in graph[cur_node]:
if isVisited[next_node]:
continue
if cur_usado < next_usado:
next_usado = cur_usado
if next_usado >= k:
queue.append((next_node, next_usado))
isVisited[next_node] = True
answer += 1
print(answer)
n, q = map(int, input().split())
graph = {}
for _ in range(n - 1):
pi, qi, ri = map(int, input().split())
if pi in graph:
graph[pi].append((qi, ri))
else:
graph[pi] = [(qi, ri)]
if qi in graph:
graph[qi].append((pi, ri))
else:
graph[qi] = [(pi, ri)]
for _ in range(q):
k, v = map(int, input().split())
bfs(k, v)
'Problem Solving > Python' 카테고리의 다른 글
[백준]BOJ 14499: 주사위 굴리기 - Python (0) | 2024.04.15 |
---|---|
[백준]BOJ 5558: チーズ (Cheese) - Python/BFS (0) | 2024.04.12 |
[백준]BOJ 10021: Watering the Fields - Python/Kruskal (0) | 2024.04.12 |
[백준]BOJ 14658: 하늘에서 별똥별이 빗발친다 - Python, Brute force (0) | 2024.04.07 |
[백준]BOJ 10159: 저울 - Python, Floyd-Warshall (0) | 2024.04.07 |