[LeetCode] 2192. All Ancestors of a Node in a Directed Acyclic Graph

https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/

leetcode - All Ancestros of a Node in a Directed Acyclic Graph

문제 유형 : 위상 정렬

문제 난이도 : Medium

 

문제

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

 

당신은 정수 DAG의 노드의 개수 n을 받습니다. 라벨이 0부터 n-1까지 붙어있습니다.

edges[i] = [from_i, to_i]가 from에서 to로의 방향이 있는 간선을 나타냅니다. edges는 2D배열입니다.

answer[i]가 i번째 노드의 조상 노드들을 오름차순으로 가지고 있는 배열이 되도록 2D배열 answer를 만들어서 반환하시오.

 

풀이

간선을 조사하여 그래프와 진입차수를 저장한다.

진입차수가 0인 곳들부터 큐에 넣는다.

answer[dst]에 answer[src(=큐의 front)]와 src를 추가한다. 그리고 진입차수를 줄이다.

그러다 dst의 진입차수가 0이 되면, 그 노드 역시 큐에 넣고 계속하면 된다.

 

 

answer에 값을 삽입하는 방법으로는 이진탐색으로 정렬된 채로 삽입시켰다.

 

코드

C++

class Solution {
public:
    void insertNum(vector<int>& arr, int num) {
        if (arr.empty()) {
            arr.push_back(num);
            return;
        }
        int left = 0;
        int right = arr.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (num == arr[mid]) return;
            else if (num > arr[mid]) left = mid + 1;
            else right = mid;
        }
        if (arr[left] == num) return;
        if (num > arr[left]) arr.insert(arr.begin() + left + 1, num);
        else arr.insert(arr.begin() + left, num);
    }

    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> answer(n);
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0);

        for (const auto &edge : edges) {
            int src = edge[0];
            int dst = edge[1];
            graph[src].push_back(dst);
            indegree[dst]++;
        }

        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (const auto &nextNode : graph[curr]) {
                for (int ancestor : answer[curr]) {
                    insertNum(answer[nextNode], ancestor);
                }
                insertNum(answer[nextNode], curr);
                if (--indegree[nextNode] == 0) {
                    q.push(nextNode);
                }
            }
        }

        return answer;
    }
};