SWEA 5102ノードの距離
問題のソースソフトウェアExpert Academy
問題の著作権はSW Expert Academyにあります.
問題の著作権はSW Expert Academyにあります.
質問の概要
- V개 노드와 E개의 간선이 주어진다.
- 출발 노드(S)에서 도착노드(G)까지 가려면 최소 몇 개의
간선을 지나야하는지 알아내는 프로그램을 작성
- 예를 들어 다음 그래프에서 1(S)에서 6(G)까지 가는데
두 번 이동하므로 2를 출력한다
プールアクセス
- 최단거리 구할 땐 bfs로 기준점 기준으로 양방향 탐색
コード#コード#
# 앞뒤로 추가와 삭제가 가능한 양방향 큐(deque)
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())
# 그래프 표시할 2차원 행렬
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(f'#{tc} {bfs(start,end)}')
1
6 5
1 4
1 3
2 3
2 5
4 6
1 6
#1 2
変数の決定
Q
deque([])
G # 노드와 간선을 나타낸 2차원 행렬 그래프
[[], [4, 3], [3, 5], [1, 2], [1, 6], [2], [4]]
visited # 방문처리 (인덱스 0 값은 무시)
[0, 1, 1, 1, 1, 1, 1]
distance # 노드별 거리표시 (인덱스 0 값은 무시)
[0, 0, 2, 1, 1, 3, 2]
Reference
この問題について(SWEA 5102ノードの距離), 我々は、より多くの情報をここで見つけました https://velog.io/@wltn39/SWEA-5102-노드의-거리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol