[SWEA] 1260. 화학물질2 - 파이썬 풀이

1258. 행렬찾기에서 조금 더 나아간 문제.

 

전략

1. 행렬찾기와 동일하게 행렬들의 크기 정보를 저장

2. 행렬곱을 할 수 있도록 크기들을 정렬

3. 행렬 원소 간의 곱셈수가 최소인 경우를 찾기 (DP 활용 - 아래 코드의 calculate_mat 함수)

 

T = int(input())

def calculate_mat(left, right):
    if left == right:
        return 0
    if DP[left][right] != -1:
        return DP[left][right]
    
    temp_result = float('inf')
    for i in range(left, right):
        temp_result1 = calculate_mat(left, i)
        temp_result2 = calculate_mat(i+1, right)
        cal_num = sorted_info[left][0] * sorted_info[i][1] * sorted_info[right][1]
        temp_result = min(temp_result, temp_result1+temp_result2+cal_num)
    
    DP[left][right] = temp_result
    return temp_result
        
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    N = int(input())

    matrix = []
    for i in range(N):
        matrix.append(list(map(int, input().split())))
    
    mat_info = []
    for i in range(N): # row
        for j in range(N): # column
            if matrix[i][j]: # 0이 아닌 경우 찾기
                w_end = j + 1
                while w_end < N and matrix[i][w_end]:
                    w_end += 1
                width = w_end - j

                h_end = i + 1
                while h_end < N and matrix[h_end][j]:
                    h_end += 1
                height = h_end - i

                mat_info.append((height, width))
                
                zero_i, zero_j = i, j
                for m in range(i, h_end):
                    for n in range(j, w_end):
                        matrix[m][n] = 0
    
    # 여기까지 matrix 정보는 다 얻었고..
    # 행렬곱을 할 수 있도록 정렬해줘야 함
    info_dict = {}
    keys = set()
    values = set()
    for m, n in mat_info:
        info_dict[m] = n
        keys.add(m)
        values.add(n)
    
    start = keys - values
    start = start.pop()

    sorted_info = []
    while len(sorted_info) < len(mat_info):
        sorted_info.append((start, info_dict[start]))
        start = info_dict[start]
    # 정렬 완료!

    # 곱이 제일 작은 걸 구해야 함.
    DP = [[-1] * len(sorted_info) for _ in range(len(sorted_info))]
    result = calculate_mat(0, len(sorted_info)-1)

    print(f"#{test_case} {result}")
    # ///////////////////////////////////////////////////////////////////////////////////