알고리즘/leetcode
[Java] leetCode 1557. Minimum Number of Vertices to Reach All Nodes
24시간이모자란
2023. 5. 18. 15:13
문제
https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/
Minimum Number of Vertices to Reach All Nodes - LeetCode
Can you solve this real interview question? Minimum Number of Vertices to Reach All Nodes - Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from
leetcode.com
정점의 집합들을 탐색했을때 모든 그래프를 탐색 가능한 최소 집합을 구하시오
풀이
vertex A , B 가 있다. (vertex는 정점)
다음과 같은 그래프 정보가 주어지면
A -> B
| outDegree(진출차수) | InDegree(진입차수) | |
| A | 1 | 0 |
| B | 0 | 1 |
A, B 정점들의 진출차수, 진입차수 정보를 알수 있다.
진입차수가 0 인 정점들의 집합이 이번 문제의 정답이다.
풀이 알고리즘은 다음과 같다.
- 진입차수 정보를 얻는다.
- 진입차수가 0 인 것들을 정답 리스트에 추가한다.
- 정답 리스트를 리턴한다.
코드
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;
}
}