[SWEA] 4871 [파이썬 S/W 문제해결 기본] 4일차 - 그래프 경로

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

# 문제 링크

swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVHzyqqe8DFAWg

SW Expert Academy

# Soultion

dfs를 이용하여 푸는 문제이다. 이 문제는 방향성이 있기때문에 15줄을 넣으면 틀리므로 주의해야 한다.

간단하게 갈 수 있는 경로는 visited를 이용하여 1로 표시한 뒤, 마지막에 20줄에서 확인한다.

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)