개발자 Lim

<아이디어>

무방향 그래프에서 모든 노드에 도달할 수 있는 정점은 결과적으로 제일 마지막으로 다른 노드를 가르키는 노드임으로

모든 노드가 가르키는 노드들을 체크해서 아무런 노드에게 지목되지 않는 노드들을 찾아 해당 노드를 반환하면 된다.

<풀이 코드>

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ans = new ArrayList<>();
        // 다른 노드에게 가르킴 당하는 노드인지 아닌지 여부를 확인하는 배열
        Boolean[] isDirectnode = new Boolean[n];
        Arrays.fill(isDirectnode,false);
        for (List<Integer> node:edges)
            isDirectnode[node.get(1)]=true;
        for (int i = 0; i < n; i++) {
            if(!isDirectnode[i])
                ans.add(i);
        }
        return ans;
    }
}