[SWEA] - 5102. ノード距離
7797 ワード
swea-問題リンク
from collections import deque
def bfs(start, end):
# 시작점설정
Q. append(start)
visited[start] = 1
while Q:
v = Q.popleft()
for w in G[v]:
# 방문하지않았다면
if not visited[w]:
# 방문처리
visited[w] = 1
# 거리설정
distance[w] = distance[v] + 1
Q.append(w)
# 도착지점에 도착했으면
if w == end:
# 거리를 반환
return distance[w]
return 0
for tc in range(1, int(input()) + 1):
V, E = map(int, input().split())
G = [[] for _ in range(V+1)]
# 방향이 없는 그래프이므로 쌍방향 설정해주기
for i in range(E):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
start, end = map(int, input().split())
visited = [0] * (V + 1)
distance = [0] * (V + 1)
Q = deque()
print('#{} {}'.format(tc, bfs(start, end)))
🔑 これは前に解いた迷路距離に似た問題である.最短距離を求める場合はBFSが役に立つので注意!Reference
この問題について([SWEA] - 5102. ノード距離), 我々は、より多くの情報をここで見つけました https://velog.io/@jjiani/SWEA-5102.-노드의-거리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol