[백준] 17140번: 이차원 배열과 연산 (골드4, 파이썬)

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

아이디어

구현 문제였다. 

1. time이 100 보다 커지면 종료 후 -1 출력
2. matrix[r-1][c-1]이 존재하면 종료 후 현재 time 출력
3. 위의 두 경우에 해당되지 않을 경우
   1. 행과 열 길이를 비교
      1. 행이 더 길면 R 연산
      2. 열이 더 길면 C 연산

C연산은 R연산과 같은 연산을 하되, 연산의 앞 뒤에 matrix를 전치(Transpose) 시키는 과정이 필요하다.

이 부분은 파이썬으로 쉽게 해결했다.

list(zip(*matrix))

 

연산 로직은 아래와 같다.

 

1. 각 row안에 있는 숫자와 해당 숫자의 수 세기
2. 문제 조건에 맞게 정렬
3. 가장 긴 row에 맞게 0 추가
4. 만약 row의 길이가 100이 넘어가면 0~100까지 슬라이싱
5. 변경된 matrix 리턴

calculate(matix, key): 연산 메서드

matrix에는 현재 상태의 matrix를 넣고, key에는 R 또는 C 연산의 정보를 넣는다.

def calculate(matrix, key):
    
    new_matrix, length = [], 0
    for row in matrix:
        num_count, new_row = [], []
        for num in set(row): # set으로 숫자 중복 제거
            if num == 0: continue
            cnt = row.count(num)
            num_count.append((num, cnt)) # 숫자와 갯수 추가

        num_count.sort(key=lambda x: (x[1], x[0]))

        new_row = [x for y in num_count for x in y]

        new_matrix.append(new_row)
        length = max(length, len(new_row)) # 가장 긴 길이로 업데이트

    # 0 추가
    for row in new_matrix: 
        row += [0] * (length-len(row))
        if len(row) > 100: row = row[:100]
    
    return list(zip(*new_matrix)) if key == "C" else new_matrix

 

중복을 제거할때에는 set 자료형과 count 메서드를 사용한다. set을 통해 중복 수를 제거하고, set을 loop하면서 각 수가 얼마나 있는지 count 한다.

for num in set(row): # set으로 숫자 중복 제거
    if num == 0: continue
    cnt = row.count(num)
    num_count.append((num, cnt)) # 숫자와 갯수 추가

 

이렇게 (숫자, 갯수)의 쌍을 구했으면 문제 조건에 맞게 정렬해야 한다. 우선 갯수를 기준으로 정렬하고, 그 뒤 갯수가 같으면 숫자를 기준으로 정렬한다. 

num_count.sort(key=lambda x: (x[1], x[0]))

 

그 후 튜플을 벗겨주어야 한다. [(num, count), (num, count), (num, count)] 를 [num, count, num, count, num, count] 로 바꿔주는 코드이다. 구현 문제에서 유용하니 알아두면 좋다!

new_row = [x for y in num_count for x in y]

 

이제 새로 만든 new_matrix에 new_row를 추가하면 된다. 추가하면서 추가로 length(new_matrix의 row 중 가장 긴 길이) 를 업데이트 해준다.

length = max(length, len(new_row))

 

위 로직을 matrix의 row만큼 반복하면 new_matrix가 완성된다.

이제 앞서 구한 length를 사용하여 빈 공간에 0을 채워주어야 한다.

각 row에 length-len(row)만큼의 0을 뒤에 추가해주고, row의 길이가 100을 넘으면 0~100까지 슬라이싱 해준다.

for row in new_matrix: 
    row += [0] * (length-len(row))
    if len(row) > 100: row = row[:100]

 

그 후 new_matrix를 리턴해주면 되는데, R연산은 그냥 리턴하고, C연산은 다시 전치해서 리턴하면 된다.

return list(zip(*new_matrix)) if key == "C" else new_matrix

 

전체 코드

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

matrix = [[int(x) for x in input().split()] for _ in range(3)]

def calculate(matrix, key):
    
    new_matrix, length = [], 0
    for row in matrix:
        num_count, new_row = [], []
        for num in set(row): # set으로 숫자 중복 제거
            if num == 0: continue
            cnt = row.count(num)
            num_count.append((num, cnt)) # 숫자와 갯수 추가

        num_count.sort(key=lambda x: (x[1], x[0]))

        new_row = [x for y in num_count for x in y]

        new_matrix.append(new_row)
        length = max(length, len(new_row)) # 가장 긴 길이로 업데이트

    # 0 추가
    for row in new_matrix: 
        row += [0] * (length-len(row))
        if len(row) > 100: row = row[:100]
    
    return list(zip(*new_matrix)) if key == "C" else new_matrix


r -= 1
c -= 1

time = 0
while True:
    if time > 100:
        time = -1
        break
    if  0 <= r < len(matrix) and 0 <= c < len(matrix[0]) and matrix[r][c] == k: break
    
    if len(matrix) >= len(matrix[0]): # 행 > 열 비교
        matrix = calculate(matrix, "R")
    else:
        matrix = calculate(list(zip(*matrix)), "C")
    time += 1

print(time)

 

후기

사실 처음에는 코드가 이렇게 깔끔하지 않았다. 전치행렬 생각을 못하고 matrix를 90도씩 돌리는 방법을 사용했기 때문이다. 그리고 빈 공간에 0을 채우지 않고, 100*100에 0을 채우고 시작해서 코드가 더 장황하고, 예외처리 하는 부분이 많았다.

그래서 풀고 나서 코드 가독성을 높이기 위해 여러 블로그를 찾아보던 중 아래 글을 보게 되었다. 해당 블로그에 있는 틀과 알고있는 스킬을 바탕으로 새로 복기하니, 훨씬 더 깔끔한 코드가 나와서 이 코드로 업로드하게 되었다.

 

https://velog.io/@djagmlrhks3/Algorithm-BaekJoon-17140.-%EC%9D%B4%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4%EA%B3%BC-%EC%97%B0%EC%82%B0-by-Python

[Algorithm] BaekJoon : 17140. 이차원 배열과 연산 by Python

 

또, 전치행렬에 관련해서는 아래 글을 추천한다.

https://pyengine.blogspot.com/2016/11/python-zip-transpose.html

python zip 함수를 이용한 transpose

(A^T)^T == A이다.