2392. Build a Matrix With Conditions

[zeikar]

Problem link

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

Problem Summary

배열의 크기와 행과 열에서의 원소들의 순서가 주어질 때 순서에 맞게 배열을 만드는 문제.

Solution

간단한 위상정렬 문제.
원소들의 순서를 그래프로 보면 원소들의 놓는 순서는 위상 정렬로 쉽게 얻어낼 수 있다. 얻어낸 행와 열의 순서대로 배치하면 된다.
불가능한 경우, 사이클이 있다면 빈 배열을 리턴하면 된다.

Source Code

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:

        rowGraph = defaultdict(list)
        rowIndegree = [0] * (k + 1)
        colGraph = defaultdict(list)
        colIndegree = [0] * (k + 1)

        for rc in rowConditions:
            rowGraph[rc[0]].append(rc[1])
            rowIndegree[rc[1]] += 1

        for cc in colConditions:
            colGraph[cc[0]].append(cc[1])
            colIndegree[cc[1]] += 1

        def topologicalSort(graph, indegree):
            ret = []
            queue = deque()

            for i in range(1, k + 1):
                if indegree[i] == 0:
                    queue.append(i)

            # cycle!
            if len(queue) == 0:
                return ret

            while len(queue) > 0:
                node = queue.popleft()
                ret.append(node)

                for next in graph[node]:
                    indegree[next] -= 1

                    if indegree[next] == 0:
                        queue.append(next)

            return ret

        rowsort = topologicalSort(rowGraph, rowIndegree)
        colsort = topologicalSort(colGraph, colIndegree)

        if len(rowsort) != k or len(colsort) != k:
            return []

        rpos = [0] * (k+1)
        for i, r in enumerate(rowsort):
            rpos[r] = i

        ans = [[0] * k for _ in range(k)]
        for i, c in enumerate(colsort):
            ans[rpos[c]][i] = c
        return ans