백준 25195 (Yes or yes) - java

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

 

문제

 

 N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.

투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.

투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.

오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.

조금 쉽게 말하자면 넌 뭘 골라도 날 만나게 될 거야 Twice, YES or YES 가사 중 일부

투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.

투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.

 

유형 : BFS

 

접근 방식

• 팬클럽을 만나지 않고 끝까지 갈 수 있는 경로가 한 개라도 존재하는 지 확인하면 된다.

 

코드

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

public class BOJ_25195_Yes_or_yes {

    static int n,m,k;
    static ArrayList<Integer>[] graph;
    static boolean[] v;
    static boolean[] isIt;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];

        for(int i = 1 ; i <= n ; i++) {
            graph[i] = new ArrayList();
        }

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            graph[v1].add(v2);
        }

        st = new StringTokenizer(br.readLine()," ");
        k = Integer.parseInt(st.nextToken());

        v = new boolean[n+1];
        isIt = new boolean[n+1];

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= k ; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            isIt[tmp] = true;
        }

        if(isIt[1]) {
            System.out.println("Yes");
        }else {
            System.out.println(go());
        }

        br.close();
    }

    static String go() {

        Queue<Integer> q = new ArrayDeque<>();
        q.add(1);
        v[1] = true;

        while(!q.isEmpty()) {
            int cur = q.poll();

            for(int next : graph[cur]) {
                if(!isIt[next] && !v[next]) {
                    v[next] = true;
                    q.add(next);
                }
            }

            if(graph[cur].size() == 0 && !isIt[cur]) {
                return "yes";
            }
        }

        return "Yes";
    }
}