넘치게 채우기
[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;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 1636. Sort Array by Increasing Frequency (0) | 2024.07.23 |
---|---|
[LeetCode] 2418. Sort the People (0) | 2024.07.22 |
[LeetCode] : 1605. Find Valid Matrix Given Row and Column Sums (0) | 2024.07.20 |
[LeetCode] 1380. Lucky Numbers in a Matrix (0) | 2024.07.19 |
[LeetCode] 1530. Number of Good Leaf Nodes Pairs (0) | 2024.07.18 |