230318 동굴 탐험

public static boolean solution(int n, int[][] path, int[][] order) {
    List<List<Integer>> graph = buildGraph(n, path);
    return canSearchAllRooms(n, graph, order);
}

private static boolean canSearchAllRooms(int n, List<List<Integer>> graph, int[][] order) {
    int[] before = new int[n];
    int[] after = new int[n];
    for (int[] arr : order) {
        before[arr[1]] = arr[0];
        after[arr[0]] = arr[1];
    }
    
    int numOfRoomsVisited = 0;
    int[] visited = new int[n]; 
    Queue<Integer> q = new LinkedList<>();
    if (before[0] == 0) {
        q.offer(0);
        visited[0] = 2;
    }
    while (!q.isEmpty()) {
        int curNode = q.poll();
        numOfRoomsVisited++;
        for (int nextNode : graph.get(curNode)) {
            if (visited[nextNode] == 2) {
                continue;
            }
            if (visited[before[nextNode]] != 2) {
                visited[nextNode] = 1;
                continue;
            }
            q.offer(nextNode);
            visited[nextNode] = 2;
        }
        int saveNode = after[curNode];
        if (saveNode != 0 && visited[saveNode] == 1) {
            q.offer(saveNode);
            visited[saveNode] = 2;
        }
    }
    return numOfRoomsVisited == n;
}

private static List<List<Integer>> buildGraph(int n, int[][] path) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] arr : path) {
        graph.get(arr[0]).add(arr[1]);
        graph.get(arr[1]).add(arr[0]);
    }
    return graph;
}