2021년 1학기 알고리즘응용 12주차

• 12주차 과제 - 행렬 바꾸기

• 사용 언어 : python

• 해결 날짜 : 2021-05-31

• 느낀점 및 해결 과정 :

  • 순위를 저장할 순위 행렬을 전부 1로 초기화 시켜준다.
  • 입력한 행렬을 돌며 인덱스와 같이 heapq(최소힙)에 삽입한다.

  • change_matrix 함수를 통해 입력한 행렬을 각 행과 열에 따른 순위 행렬로 변경한다. 큐가 비어 있지 않은 동안, 큐에서 우선 순위가 가장 높은 값을 pop하여 그 인덱스가 있는 행과 열을 돌며 현재 인덱스의 값보다 크고, 현재 인덱스의 우선 순위보다 작다면 우선 순위를 현재 인덱스의 우선 순위 + 1로 수정한다.

  • 시간 복잡도 :

    • 최소힙에 삽입 : O(MN) (M = 행의 개수, N = 열의 개수)
    • change_matrix : O(MN*(M+N)) (M = 행의 개수, N = 열의 개수)
    • 따라서 O(MN + MN*(M+N)) = O(K2+2K3) = O(K3) 의 시간 복잡도를 갖는다. (K = 행 또는 열의 개수)
  • 코드

  import heapq
  
  # M = 행의 개수, N = 열의 개수, matrix = 행렬, priority = 순위 행렬
  M, N = map(int, input().split())
  matrix = [list(map(int, input().split())) for _ in range(M)]
  priority = [[1]*N for _ in range(M)]
  
  # 입력한 행렬을 돌며 인덱스와 같이 heapq(최소힙)에 삽입
  hq = []
  for i in range(len(matrix)):
      for j in range(len(matrix[i])):
          heapq.heappush(hq, (matrix[i][j], i, j))
  
  
  # 입력한 행렬을 각 행과 열에 따른 순위 행렬로 변경하는 함수
  def change_matrix():
      while hq: # 큐가 비어 있지 않을 때 반복
          val, row, col = heapq.heappop(hq)
          prior = priority[row][col] # 현재 우선 순위
          # 현재 인덱스의 행과 열을 돌며
          # 현재 인덱스의 값보다 크고, 현재 인덱스의 우선 순위보다 작다면
          # 우선 순위를 현재 인덱스의 우선 순위 + 1
          for i in range(M):
              if val < matrix[i][col] and prior >= priority[i][col]:
                  priority[i][col] = prior + 1
          for j in range(N):
              if val < matrix[row][j] and prior >= priority[row][j]:
                  priority[row][j] = prior + 1
  
  
  change_matrix()
  for i in priority:
      for j in i:
          print(j, end=' ')
      print()