[백준] 25195: Yes or yes - JAVA

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

 

풀이

방향그래프가 주어지고, 1번 정점에서 출발해 리프노드까지 도달해야한다.

 

이때, 팬클럽이 위치하는 정점들을 피해 리프노드까지 도달할 수 있는지 확인하는 문제이다.

 

dfs탐색의 인자로 팬클럽을 만났는지 여부를 담아 진행했다.

 

리프노드에 갔을 때 팬클럽을 만난적이 없다면 boolean값을 갱신해준다.

 

방문처리를 하지 않고 진행했는데 그 이유는

 

주어진 그래프가 사이클이 없음이 보장되었고,

 

방문처리를 할 경우 1 -> 2 -> 4 의 루트로 여행했다면, 1 -> 3 -> 4 의 루트로 여행하는 것은 이미 4번 정점이 방문처리 되었기 때문에 진행이 안되는 문제가 있었기 때문이다.

 

따라서, 방문처리 없이 바로 이전 정점으로만 갈 수 없게 했다.

 

---

 

메모리: 81136KB
시간: 496ms
언어: Java 11

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

public class Main {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] fanClub;
    static boolean success;

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

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
        }

        int s = Integer.parseInt(br.readLine());

        fanClub = new boolean[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < s; i++) {
            int a = Integer.parseInt(st.nextToken());
            fanClub[a] = true;
        }

        success = false;
        dfs(1, fanClub[1]);

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

    private static void dfs(int node, boolean fan) {
        boolean flag = false;
        for (int next : graph.get(node)) {
            if (next != node) {
                flag = true;
                if (fanClub[next]) {
                    dfs(next, true);
                } else {
                    dfs(next, fan);
                }
            }
        }

        if (!flag) {
            if (!fan) {
                success = true;
            }
            return;
        }
    }

}