[백준 17140번] 이차원 배열과 연산

17140번: 이차원 배열과 연산

r,c,k = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(3)]
answer = 0

def transpose(arr):
    return list(zip(*arr))

def calculate_row(index):
    row = arr[index]
    temp_dict = dict()
    sorted_row = []
    
    for i in row:
        if i == 0:
            continue
        if i in temp_dict:
            temp_dict[i] += 1
        else:
            temp_dict[i] = 1
    #print(temp_dict) # {1: 2, 2: 1}
    
    temp_list = [(i,temp_dict[i]) for i in temp_dict.keys()]
    #print(temp_list) # [(1, 2), (2, 1)]

    temp_list = sorted(temp_list, key=lambda x:(x[1],x[0]))
    #print(temp_list) # [(2, 1), (1, 2)]

    for i in temp_list:
        sorted_row.append(i[0])
        sorted_row.append(i[1])
    #print(sorted_row) # [2, 1, 1, 2]
    
    if len(sorted_row) > 100: # 정렬된 결과의 크기가 100이 넘어가면 나머지 버리기
        sorted_row = sorted_row[:100]

    return sorted_row

while True:

    if 0 <= r-1 < len(arr) and 0 <= c-1 < len(arr[0]):
        if arr[r-1][c-1] == k: # A[r][c]에 들어있는 값이 k가 되면 반복문을 멈추고 최소 시간을 출력
            break
    
    if answer > 100: # 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력
        answer = -1
        break

    answer += 1

    temp = []

    if len(arr) >= len(arr[0]): # 행의 개수 ≥ 열의 개수인 경우
        for i,value in enumerate(arr):
            temp.append(calculate_row(i))
        max_length = max([len(item) for item in temp]) # 가장 큰 행/열 크기

        for i in range(len(temp)): # 가장 큰 행/열 크기에 맞춰 0으로 채우기
            if len(temp[i]) < max_length:
                temp[i] += ([0]*(max_length-len(temp[i])))

        if len(temp) > 100: # 행 또는 열의 크기가 100을 넘어가는 경우 나머지 버리기
            temp = temp[:100]
        arr = temp
    else: # 행의 개수 < 열의 개수인 경우
        arr = transpose(arr) # 열을 행으로 처리하기 위해 잠시 전치 처리
        for i,value in enumerate(arr):
            temp.append(calculate_row(i))

        max_length = max([len(item) for item in temp]) # 가장 큰 행/열 크기

        for i in range(len(temp)): # 가장 큰 행/열 크기에 맞춰 0으로 채우기
            if len(temp[i]) < max_length:
                temp[i] += ([0]*(max_length-len(temp[i])))

        if len(temp) > 100: # 행 또는 열의 크기가 100을 넘어가는 경우 나머지 버리기
            temp = temp[:100]
        arr = transpose(temp) # 모든 처리를 해준 후 다시 전치 처리

print(answer)

이번 문제는 3 x 3 크기의 배열을 매 초마다 주어진 조건에 맞게 정렬하고, 만약에 주어진 입력 A[r][c]의 배열 값이 k와 일치할 때까지 걸리는 최소 시간을 구하는 문제이다.

 

먼저 이 문제를 보자마자 '주어진 행을 정렬하는 함수'와 '주어진 열을 정렬하는 함수'를 떠올렸다. 그런데 행 정렬은 간단하게 되었는데, 열을 정렬하자니 과정이 상당히 복잡하다는 것을 알게 되었다.

 

따라서 주어진 배열을 전치처리(행과 열을 뒤바꿈)하여 더 간단하게 풀이하기로 하였고, 그 과정에서 zip 함수에 대해서 공부하게 되었다.

 

나머지는 문제 조건에 대한 예외 처리라서 크게 어려움 없이 마무리할 수 있었다.

 

배운 점 및 느낀 점

1. zip 함수를 사용하면 동일한 개수로 이루어진 자료형을 간편하게 묶을 수 있고 간편하게 전치행렬을 만들 수 있다.
2. 주어진 배열의 크기에 맞게 0을 채우기 위해서는 (전체 길이-현재 길이) 만큼 배열을 선언하여 이어주면 된다.