코딩테스트/SWEA
[SWEA] 4871 [파이썬 S/W 문제해결 기본] 4일차 - 그래프 경로
Jiwon_C
2021. 5. 15. 23:25
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
# 문제 링크
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
# Soultion
dfs를 이용하여 푸는 문제이다. 이 문제는 방향성이 있기때문에 15줄을 넣으면 틀리므로 주의해야 한다.
간단하게 갈 수 있는 경로는 visited를 이용하여 1로 표시한 뒤, 마지막에 20줄에서 확인한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def dfs(v):
visited[v] = 1
for i in graph[v]:
if visited[i]==0:
dfs(i)
t = int(input())
for tc in range(1,t+1):
v,e = map(int,input().split())
graph = [[]*v for _ in range(v+1)]
visited = [0]*(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()) #s출발 g도착
dfs(s)
if visited[g]==1:
print("#"+str(tc),1)
else:
print("#"+str(tc),0)
|
cs |