99클럽 코테 스터디 11일차 TIL + DFS

https://www.acmicpc.net/problem/25195

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)

s = int(input())
bearList = list(map(int, input().split()))

flag = False
def dfs(v):
    global flag
    if v in bearList: # 팬을 만난 경우
        return
    
    if graph[v] == []: # 시작노드에 간선이 없다면 투어는 끝
        flag = True
        return
        
    for i in graph[v]:
        if graph[i] != []: # i에 이어져있는 간선이 있을 때
            dfs(i)
        elif graph[i] == [] and i not in bearList: # leafnode 이고 팬을 만나지 않았다면
            flag = True

dfs(1)
if flag == False:
    print("Yes")
else:
    print("yes")

• 팬을 만나지 않고 leafnode에 도착한다면 yes, 팬을 만난다면 Yes를 출력한다. 이때, 간선을 따라서 이동할 수 없는 경우엔 여행이 종료된다.
• 첫번째 if문은 팬을 만난 경우에 return을 함으로써 함수가 끝나는 것이 아닌 재귀함수로 dfs함수를 짰기 때문에 직전 노드로 다시 올라가는 것이다.
• 두번째 if문은 애초에 시작노드의 간선이 없다면 투어는 바로 끝이나므로 yes를 출력한다.
• for문을 통해 i에 이어진 간선이 있다면 dfs를 호출하고 i에 이어진 간선이 없고 즉, leafnode이고 팬을 만나지 않았다면 yes를 출력할 수 있도록 한다.