[Java] leetCode 1557. Minimum Number of Vertices to Reach All Nodes

문제

https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/

Minimum Number of Vertices to Reach All Nodes - LeetCode

정점의 집합들을 탐색했을때 모든 그래프를 탐색 가능한 최소 집합을 구하시오

풀이

vertex A , B 가 있다. (vertex는 정점) 

다음과 같은 그래프 정보가 주어지면

A -> B 

	outDegree(진출차수)	InDegree(진입차수)
A	1	0
B	0	1

A, B 정점들의 진출차수, 진입차수 정보를 알수 있다.

진입차수가 0 인 정점들의 집합이  이번 문제의 정답이다. 

 

풀이 알고리즘은 다음과 같다.

1. 진입차수 정보를 얻는다.
2. 진입차수가 0 인 것들을 정답 리스트에 추가한다.
3. 정답 리스트를 리턴한다.

 

코드

class Solution {

    boolean[] hasInDegree;

 

    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {

 

        hasInDegree = new boolean[n];

 

        for(List<Integer> l : edges){

            hasInDegree[l.get(1)] = true;//진입 차수 정보를 얻는다.

        }

 

        List<Integer> l = new ArrayList<>();//

 

        for(int i =0 ; i < n; i++){

            if(!hasInDegree[i]){ //진입차수가 0 인 것들을 정답 리스트에 추가한다.

                l.add(i);

            }

        }

 

        return l;

 

    }

}