99클럽 코테 스터디 11일차 TLI(BFS)

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

제한 조건

• 첫째 줄에는 정점의 개수
• 정점의 개수: $N$, 간선의 개수: $M$ ($1 \leq N, M \leq 100\,000$)
• $M+2$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수
• $M+3$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호
• 팬클럽 곰곰이를 만나게 된다면 "Yes"
• 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes"(한번이라도 곰곰이를 만나면 Yes)

🚨오늘의 학습

⭐️BFS⭐️

수평 구조의 이동 거리 탐색시 효율적이다
그리고 경로를 같은 깊이에서 검사하기 때문에 특정 깊이에서 팬클럽 곰곰이를 만나면 더 깊은 경로까지 탐색할 필요가 없습니다.
그래서 DFS 보다 효율적이라고 판단하여 선택

🗝️ 곰곰이를 만나지 않는 경로가 하나라도 있다면 yes
※ Boolean으로 TRUE/FALSE

🗝️ 곰곰이가 없는 위치 && 더 이상 진행할 경로 없음(마지막 위치)

import java.util.*;
import java.io.*;

public class Main {
    static ArrayList<ArrayList<Integer>> graph;
    static Boolean canAvoid = false;
    static int[] visited ;
    static Queue<Integer> queue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int node = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        visited = new int[node+1];
        queue = new LinkedList<>();


        graph = new ArrayList<>(node+1);
        for(int i=0; i<=node;i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0; i<edge; i++){
            st = new StringTokenizer(br.readLine());

            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            graph.get(node1).add(node2);
        }

        st = new StringTokenizer(br.readLine());
        int gomCnt = Integer.parseInt(st.nextToken());
        List<Integer> gomArr = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<gomCnt;i++){
            gomArr.add(Integer.parseInt(st.nextToken()));
        }

        queue.add(1);

        while(!queue.isEmpty()){
            int now = queue.poll();
            visited[now]=1;

            if(gomArr.contains(now)){
                continue;
            }

            if(graph.get(now).isEmpty()){
                canAvoid = true;
                continue;
            }

            for (Integer connect : graph.get(now)) {
                if(visited[connect]==0){
                    queue.add(connect);
                }
            }

        }
        System.out.println( canAvoid?"yes":"Yes");


    }


}