23.04.09. 풀었던 문제들

Leetcode 1857. Largest Color Value in a Directed Graph

 문제를 읽고, 일단 귀찮은 문제라는 것은 깨달았다. 해야 하는 것만 해도

• cycle 존재 여부 검증
• cycle이 없는 경우, 모든 path에 대해 모든 색깔의 경우의 수를 구해야 한다.

 이 문제의 경우 outgoing edge가 1개라는 조건이 없기 때문에 일반적인 directed graph에서 cycle 여부를 검증하는 방법을 사용해야 했고, 모든 path를 탐색해야 한다는 점에서 topological sort가 떠올랐다. 그러나 topological sort를 사용한 지 오래되어서 해당 구현은 이전에 쓴 게시글을 참고했다. 

 

 topological sort의 큰 로직은 아래와 같다.

• source vertex를 찾고 모든 source를 queue에 넣는다. ... 1
• q의 front()와 해당 vertex에 연결된 adjacent vertex로의 edge를 graph에서 삭제한다.  ... 2
  • 이 때 graph에서 직접 삭제하지 말고, incoming edge 개수를 따로 저장해둔 후 이 단계에서 q.front()와 q.front()의 adj를 잇는 edge의 incoming edge 개수를 1 줄인다.
  • 만약 adj의 incoming edge 개수가 0이라면 q에 push한다.
• 모든 graph의 edge에 대해 탐색한다.
• 만약 탐색이 끝나기 전 queue size가 0이라면 source vertex가 없는 것이므로, 즉 cycle이 있는 것을 의미한다. 만약 queue size가 1보다 크다면 topological sort 결과가 2개 이상이라는 것이다.
• 이 경우 시간복잡도는 O(V + E)이다.

 

 이 문제의 경우 connected directed graph이므로 queue size가 0이 되는지 여부만 탐색하면 cycle 여부를 알 수 있다.

 이렇게 cycle 여부를 알아낸 뒤에는 모든 path에 대해 모든 색깔의 경우의 수를 탐색해 주어야 한다. 우리는 이미 topological sort를 통해 path의 진행방향으로만 vertex를 탐색한다. 따라서 배열 하나를 추가한다.

• num_color[v][c]는 vertex v까지 탐색했을 때, color c의 개수이다.
• q.pop()을 했다는 것은 source vertex 하나가 줄어드는 것이며, 해당 vertex까지 path를 탐색했다는 것이다. 이 때 해당 vertex의 color는 반영되지 않았으므로 num_color[front][color[front]-'a']++을 해 주고, 정답을 같이 갱신해 준다. ... 3-1.
• 또한 q.front()의 adjacent vertex를 탐색할 때, q.front()의 num_color를 이용해 q.front().adjacent의 num_color도 갱신해 준다. ... 3-2.

class Solution {
public:
    int n;
    vector<vector<int>> edges;
    vector<int> num_income;
    int largestPathValue(string colors, vector<vector<int>>& e) {
        // initialize
        n = colors.size();
        edges.resize(n);
        num_income.resize(n); // ... 1. source를 찾기 위함.
        for(vector<int> vi : e){
            edges[vi[0]].push_back(vi[1]);
            num_income[vi[1]]++;
        }

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

        bool hasCycle = false;
        vector<vector<int>> num_color(n, vector<int>(26, 0)); // num_color[v][c] : vertex v까지 탐색했을 때 color c가 나온 회수
        int answer = -1;
        for(int i = 0; i<n; i++){
            if(q.empty()){
                return -1;
            }

            int front = q.front(); q.pop();
            num_color[front][colors[front] - 'a']++;
            answer = max(answer, num_color[front][colors[front] - 'a']); /// ... 3-1.
            
            // ... 2.
            for(int adj : edges[front]){
                num_income[adj]--;
                if(num_income[adj] == 0) q.push(adj);

                // ... 3-2.
                for(int i = 0; i<26; i++){
                    num_color[adj][i] = max(num_color[front][i], num_color[adj][i]);
                }
            }
        }

        return answer;
    }
};

 

시간복잡도

 topological sort에 O(V + E), V = n, E = m이므로 O(n+m)이다. 그리고 각 탐색에서 size 26만큼의 for문을 돌리지만 이는 시간복잡도에 영향을 주지는 않는다. 따라서 O(n+m).

 

공간복잡도

 q에 worst case O(V)만큼 들어가고 edge에 O(E), num_income에 O(V), num_color에 O(V)만큼 들어가므로 O(n+m)이다.

 

후기

 topological sort에 dp를 적용하는 문제였다. 빡셌다.