[LeetCode] 2392. Build a Matrix With Conditions

https://leetcode.com/problems/build-a-matrix-with-conditions/description/

leetcode - Build a Matrix With Conditions

문제 유형 : 행렬, 위상 정렬

문제 난이도 : Hard

 

문제

You are given a positive integer k. You are also given:

• a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and
• a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].

The two arrays contain integers from 1 to k.

You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0.

The matrix should also satisfy the following conditions:

• The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.
• The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

 

양의정수 k를 받는다. 그리고, 두 개의 2D배열 rowConditions와 colConditions를 받는다.

rowConditions[i] = [above_i, below_i],

colConditions[i] = [left_i, right_i]이다.

 

두 배열은 1부터 k까지 주어진다.

k x k의 행렬을 만들어서 반환해야 한다.

1부터 k까지의 수를 하나씩 채워야 하고, 나머지는 0이어야 한다.

above_i의 수는 below_i의 수보다 반드시 위 행에 있어야 한다.

left_i의 수는 right_i의 수보다 반드시 왼쪽 열에 있어야 한다.

 

조건에 맞게 행렬을 만들어서 반환한시오. 안만들어진다면, 빈 행렬을 넣으시오.

 

풀이

 

각 rowConditions, colConditions를 읽으면서, 그래프인 rowGraph, colGraph를 만든다.

인접차수를 각각 저장하는 rowIndegree, coIndegree를 만든다.

각 숫자의 의존성 관계를,

avobe -> below,

left -> right으로 하였다.

 

이제, 위상정렬을 통해서 숫자의 관계를 선형적으로 정리해주면 된다.

row, col 각각에 대해서 위상정렬을 한다. 인접차수가 0인 숫자부터 시작해서, 의존하고 있는 다음 숫자들의 인접차수를 1씩 줄이면서 또 0이 되면 큐에 넣음을 반복한다. 그 과정에서 배열에 선형적으로 순서를 저장한다.

만약 배열의 크기가 k와 다르다면, 사이클이 존재한다는 유효하지 않은 관계가 있다는 뜻이다.

이런 경우, 빈 배열을 반환한다.

 

만약 row, col 각각에서의 정렬된 배열이 빈 배열이라면, 유효하지 않으므로 빈 행렬을 반환한다.

그게 아니라면, 정렬된 배열들을 통해서 행렬에 1부터 k까지 숫자로 채워주면 된다.

k * k의 크기에 1 ~ k를 넣는 것이므로, 같은 행 또는 열에 같은 숫자가 오게 하지 않을 수 있어서 편하게 만들 수 있다.

 

코드

C++

class Solution {
public:
    vector<int> topologicalSort(int k, vector<vector<int>>& graph, vector<int>& indegree) {
        vector<int> order;
        queue<int> q;
        for (int i = 1; i <= k; i++) {
            if (indegree[i] == 0) q.push(i);
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            order.push_back(curr);
            for (const int &next : graph[curr]) {
                indegree[next]--;
                if (indegree[next] == 0) q.push(next);
            }
        }

        if (order.size() == k) return order;
        else return {};
    }

    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<vector<int>> rowGraph(k + 1);
        vector<int> rowIndegree(k + 1, 0);
        for (const auto &cond : rowConditions) {
            rowGraph[cond[0]].push_back(cond[1]);
            rowIndegree[cond[1]]++;
        }

        vector<vector<int>> colGraph(k + 1);
        vector<int> colIndegree(k + 1, 0);
        for (const auto &cond : colConditions) {
            colGraph[cond[0]].push_back(cond[1]);
            colIndegree[cond[1]]++;
        }

        vector<int> rowOrder = topologicalSort(k, rowGraph, rowIndegree);
        vector<int> colOrder = topologicalSort(k, colGraph, colIndegree);

        if (rowOrder.empty() || colOrder.empty()) return {};

        vector<int> rowPosition(k + 1, 0);
        vector<int> colPosition(k + 1, 0);
        for (int i = 0; i < k; ++i) {
            rowPosition[rowOrder[i]] = i;
            colPosition[colOrder[i]] = i;
        }

        vector<vector<int>> matrix(k, vector<int>(k, 0));
        for (int i = 1; i <= k; ++i) {
            matrix[rowPosition[i]][colPosition[i]] = i;
        }

        return matrix;
    }
};