[boj 25195] Yes or yes

문제 링크

 

문제 자체는 bfs만 돌려도 풀리는 문제였습니다.

 

다만, 문제 설명에서 투어리스트 곰곰이가 여행의 마지막 노드에서 팬클럽 곰곰이를 만나는 경우는, 투어리스트 곰곰이가 성공적으로 여행을 완료한 판정입니다.

 

이를 주의하면 다른 문제는 없으리라 생각됩니다.

 

import sys
from collections import deque

input = sys.stdin.readline


def bfs(V, G):
    q = deque([1])
    
    V[1] = 0
    
    while q:
        n = q.popleft()
        
        if not G[n]:
            return "yes"
        
        for x in G[n]:
            if not V[x]:
                V[x] = 1
                q.append(x)
                
    return "Yes"


def solve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N+1)]
    
    for _ in range(M):
        u, v = map(int, input().split())
        G[u].append(v)
        
    S = int(input())
    
    Ss = list(map(int, input().split()))
    
    V = [0] * (N+1)
    
    for s in Ss: V[s] = 1
    
    if V[1]:
        print("Yes")
        return
    
    print(bfs(V, G))
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()