BOJ_2617 구슬 찾기 Gold.4

무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다.

문제의 요구 사항은 중간인 구슬이 절대 될 수 없는 구슬의 개수를 구하는 것이다.
이 말은 즉, 각 구슬이 무거운 것 또는 가벼운 것이 중간인 구슬의 순서 번호보다 많거나 같으면 절대 중간이 될 수 없다는 말이다

따라서
1. 그래프를 만들 줄 알아야함
2. 탐색하여 개수를 세면 됨

나는 방문기록을 체크하지 않아서 처음에 시간초과가 났다! 이런 실수하면 안된다...

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static class Node {
        Set<Node> prev = new HashSet<>();
        int index;
        Set<Node> next = new HashSet<>();

        public Node(int index) {
            this.index = index;
        }
    }
    private static int N, M, middle;
    private static List<Node> graph = new ArrayList<>();
    private static boolean[] nextVisited;
    private static boolean[] prevVisited;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= N; i++) {
            graph.add(new Node(i));
        }

        middle = (N + 1) / 2; // 중간이 되는 구슬 번호

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int heavy = Integer.parseInt(st.nextToken()), light = Integer.parseInt(st.nextToken());

            Node heavyNode = graph.get(heavy);
            Node lightNode = graph.get(light);

            lightNode.next.add(heavyNode);
            heavyNode.prev.add(lightNode);
        }


        for (int i = 1; i <= N; i++) {
            Node node = graph.get(i);
            prevVisited = new boolean[N + 1];
            nextVisited = new boolean[N + 1];

            if (dfs(node, 0) >= middle) {
                answer++;
            } else if (revDfs(node, 0) >= middle) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    private static int dfs(Node node, int count) {
        nextVisited[node.index] = true;

        for (Node next : node.next) {
            if (!nextVisited[next.index]) {
                count = dfs(next, count + 1);
            }
        }
        return count;
    }

    private static int revDfs(Node node, int count) {
        prevVisited[node.index] = true;

        for (Node prev : node.prev) {
            if (!prevVisited[prev.index]) {
                count = revDfs(prev, count + 1);
            }
        }
        return count;
    }
}