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

문제 보기

이 문제는 시뮬레이션 문제이다.

처음에 문제를 읽자마자 든 생각은 두 가지였다.

1. collections 모듈의 Counter 자료구조를 사용해야겠다.
2. 행과 열에 대한 연산이 있으므로, 열에 대한 연산은 A 행렬을 transpose 시켜야겠다.

이 두 가지 생각을 잘 구현하니 AC를 받았다.

 

문제를 푼 로직은 다음과 같다.

1. 행렬 A를 초기 상태의 3 * 3 행렬로 초기화한다. (5~9번째 줄)
2. R연산) A의 각 행마다 (숫자, 숫자가 나타난 횟수)의 리스트를 생성하고, 그 리스트에 대해 (숫자가 나타난 횟수, 숫자) 순으로 오름차순으로 정렬한다. (17번째 줄)
3. R연산) 정렬된 0이 아닌 숫자들을 해당하는 A의 행에 새롭게 대입시킨다. (19~24번째 줄)
4. R연산을 통해 바뀐 열의 최대 길이를 갱신하고, 나머지 칸들은 0으로 지정한다. (25~28번째 줄)
5. C연산) A의 전치 행렬을 구한다. (31~32번째 줄)
6. C연산) A의 전치 행렬의 각 행마다 (숫자, 숫자가 나타난 횟수)의 리스트를 생성하고, 그 리스트에 대해 (숫자가 나타난 횟수, 숫자) 순으로 오름차순으로 정렬한다. (A의 전치 행렬의 각 행에 대해 실행한 연산 == A의 각 열에 대해 실행한 연산) (34번째 줄)
7. C연산) 정렬된 0이 아닌 숫자들을 해당하는 A의 열에 새롭게 대입시킨다. (36~41번째 줄)
8. C연산을 통해 바뀐 열의 최대 길이를 갱신하고, 나머지 칸들은 0으로 지정한다. (42~45번째 줄)
9. 정답을 찾거나, 연산 횟수가 100번을 넘어갈 때까지 1~8번을 반복한다. (12번째 줄)

 

사용하면 할수록 느끼는 거지만, collections 모듈의 Counter 자료구조와 zip 함수는 매우 유용한 것 같다.

 

import sys
from collections import Counter
 
r, c, k = map(int, sys.stdin.readline().strip().split())
A = [[0 for _ in range(101)] for _ in range(101)]
for i in range(3):
    line = list(map(int, sys.stdin.readline().strip().split()))
    for j in range(3):
        A[i][j] = line[j]
 
answer, max_r, max_c = 0, 3, 3
while A[r - 1][c - 1] != k and answer < 101:
    # operation R
    if max_r >= max_c:
        # for all rows
        for i in range(max_r):
            sorted_row = list(sorted(Counter(A[i]).items(), key=lambda x: (x[1], x[0])))
            
            j = 0
            for key, occurrence in sorted_row:
                if key != 0:
                    A[i][j] = key
                    A[i][j + 1] = occurrence
                    j += 2
            max_c = max(max_c, j)
            # set rest of blanks to 0
            for j in range(j, 101, 1):
                A[i][j] = 0
    # operation C
    else:
        # transposed matrix of A
        transposed_A = list(zip(*A))
        for j in range(max_c):
            sorted_col = list(sorted(Counter(transposed_A[j]).items(), key=lambda x: (x[1], x[0])))
            
            i = 0
            for key, occurrence in sorted_col:
                if key != 0:
                    A[i][j] = key
                    A[i + 1][j] = occurrence
                    i += 2
            max_r = max(max_r, i)
            # set rest of blanks to 0
            for i in range(i, 101, 1):
                A[i][j] = 0
    answer += 1
 
if answer < 101:
    print(answer)
else:
    print(-1)