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

leetcode 답게 문제에서 요구하는 바는 간단했습니다.

DAG가 주어졌을떄, 각 노드에서 경로를 따라 도달할 수 있는 노드들의 리스트를 구하고

이렇게 구한 리스트들을 최소한으로 조합하여 모든 노드들을 커버하는 케이스를 구하라는 것이다.,

 

음,, 우선 각 노드에서 도달할 수 있는 노드들의 리스트를 구해야 했으니

플로이드 와셜 알고리즘이 떠올랐다.

떠오르자 마자 해당 알고리즘을 쓰면 소스가 무지하게 더럽게 나올 것 같단걸 예상했지만 우선 시도해보았습니다.,

 

역시 더럽더군요,,,

중간에 포기하고 새로운 아이디어를 생각해보다가

그냥 단순히 들어오는 경로가 없는 노드들을 출력하면 되는 거였더군요

어차피 들어오는 경로가 없는 노드들은 필연적으로 답에 포함되는 노드들이기 때문에

들어오는 경로가 없는 노드들만을 조합해서 모든 노드들을 커버하는 경로를 만드는지를 증명하면 되는건데,,

 

직관적으로 만일 해당 노드들만으로 커버하지 못하는 노드가 있다면

해당노드는 반드시 들어오는 경로가 없는 노드일 것이기 때문에 초기 조건에 배반이 됩니다.

그렇기에 위의 가정은 참이되면서 문제는 굉장히 간단해졌습니다.,

 

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> check(n, 0);
        vector<int> ret;
        for(vector<int> e : edges) check[e[1]]++;
        
        
        for(int i = 0; i<n; i++){
            if(check[i] == 0) ret.push_back(i);
        }
        
        return ret;
    }
};

 

시간복잡도는 O(n) 이고,

속도가 30%대로 그리 빠른건 아닌데, 90이상 나온 소스와 비교했을때 소스의 구현방식의 차이일 뿐 접근방식은 차이가 없더라구요

이정도면 충분할 것 같습니다.