[BOJ] 백준 25195. Yes or yes

문제

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

25195번: Yes or yes

---

풀이

 BFS, DFS 문제입니다. 문제의 포인트는 팬클럽 곰곰이를 거치지 않고 더 이상 이동할 수 없는 간선까지 도달할 수 있는가? 입니다.

 

 우선 팬클럽 곰곰이의 정점을 boolean[] gomgom 배열에 저장해두었습니다. 그리고 BFS 탐색시에 gomgom 배열을 체크합니다. 만약 현재의 정점이 gomgom[] 배열의 true 라면, continue를 통해 더 이상 진행하지 못하도록 조건을 걸었습니다. 

 

 위 조건을 피해서 정점의 끝까지 도달했다면 정점의 끝이라는 조건 즉, 해당 정점에 더 이상 간선이 없다는 조건인 list[now].isEmpty() 조건을 통해 return 값을 "yes"로 반환해주었습니다.

 

 위에서의 로직에 해당하지 않는다면, 끝까지 도달하지 못했다는 것임으로 "Yes" 를 반환합니다.

 

---

소스코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class B25195_yesoryes {

    static int N,M;
    static ArrayList<Integer>[] list;
    static boolean[] gomgom;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        list = new ArrayList[N+1];
        gomgom = new boolean[N+1];
        for(int i=0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 0;i<M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            list[st].add(ed);
        }
        int S = sc.nextInt();
        for(int i =0;i<S;i++){
            int num = sc.nextInt();
            gomgom[num] = true;
        }
        System.out.println(bfs());
    }
    static String bfs(){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        while(!queue.isEmpty()){
            int now = queue.poll();
            if(gomgom[now]) continue;
            if(list[now].isEmpty()) return "yes";
            for(int next : list[now]){
                queue.add(next);
            }
        }
        return "Yes";
    }
}