코딩테스트/SWEA
[SWEA] 5102 [파이썬 S/W 문제해결 기본] 6일차 - 노드의 거리
Jiwon_C
2021. 6. 1. 23:52
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
# 문제 링크
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
# Soultion
최소거리를 구하는 문제이므로 bfs를 사용
|
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
|
from collections import deque
t = int(input())
for tc in range(1,t+1):
v,e = map(int,input().split())
graph = [[]for _ in range(v+1)]
for _ in range(e):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
s,g =map(int,input().split())
queue = deque([s])
visited = [0]*(v+1)
visited[s]=1
while(queue):
n = queue.popleft()
for i in graph[n]:
if visited[i]==0:
queue.append(i)
visited[i] = visited[n]+1
if visited[g]!=0:
print("#"+str(tc),visited[g]-1)
else:
print("#"+str(tc),0)
|
cs |