파이썬에서 행과 열 합이 주어진 유효한 행렬을 찾는 프로그램

rowSum[i]에는 i번째 행에 있는 요소의 합이 있고 colSum[j]에는 2D 행렬의 j번째 열에 있는 요소의 합이 있는 음수가 아닌 값을 가진 두 개의 배열 rowSum 및 colSum이 있다고 가정합니다. 주어진 rowSum 및 colSum 값을 만족하는 크기(rowSum 크기 x colSum 크기)의 음이 아닌 값을 가진 행렬을 찾아야 합니다.

따라서 입력이 rowSum =[13,14,12] colSum =[9,13,17]과 같으면 출력은

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 행렬 :=빈 행렬 생성
• 방문함:=새로운 세트
• minimum() 함수를 정의합니다. r,c
가 걸립니다.
• min_total :=무한대
• 유형 :=빈 문자열
• 0에서 r - 1 사이의 범위에 있는 i에 대해
  • r[i]
  • 인덱스 :=나
  • 유형 :='행'
  • min_total :=r[i]

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(r, c):
   matrix = [[0]*len(c) for _ in range(len(r))]
   visited = set()

   def minimum(r,c):
      min_total = float('inf')
   
      type = ''
      for i in range(len(r)):
         if(r[i] < min_total):
            index = i
            type = 'row'
            min_total = r[i]

      for i in range(len(c)):
         if(c[i] < min_total):
            min_total = c[i]
            type = 'col'
            index = i

      if(type == 'row'):
         r[index] = float('inf')

         for i in range(len(c)):
            if(c[i] != float('inf') and c[i] >= min_total):
               c[i] -= min_total
               matrix[index][i] = min_total
               break

      if(type == 'col'):
         c[index] = float('inf')
         for i in range(len(r)):
            if(r[i] != float('inf') and r[i] >= min_total):
               r[i] -= min_total
               matrix[i][index] = min_total
               break

      visited.add((index,type))

   while len(visited) != len(r)+len(c):
      minimum(r,c)

   return matrix

rowSum = [13,14,12]
colSum = [9,13,17]
print(solve(rowSum, colSum))

입력

[13,14,12], [9,13,17]

출력

[[9, 4, 0], [0, 9, 5], [0, 0, 12]]