[Python/BOJ] 17140. 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

풀이

Code

import sys
from collections import Counter
input = sys.stdin.readline

def solution(r, c, k, graph) :
    # 1. 현재 (r, c) 값이 k일 경우
    if r <= 3 and c <= 3 and graph[r-1][c-1] == k : print(0)
    else :
        # 2.
        for ans in range(1, 101) :
            col = False
            # 2-1. C 연산의 경우 행 / 열 뒤집기
            if len(graph) < len(graph[0]) :
                graph = list(zip(*graph))
                col = True
            # 2-2.
            for i in range(len(graph)) :
                line = graph[i]
                # 카운팅
                # 정렬
                counter = sorted(Counter(line).items(), key=lambda x: [x[1], x[0]])
                # 결과값 삽입
                ins_array = []
                for x, y in counter :
                    if x : ins_array += [x, y]
                graph[i] = ins_array
            # 2-3. 열의 최대 길이 구하기
            max_len = max([len(line) for line in graph])
            # 2-4. 제로 패딩
            for i in range(len(graph)) :
                graph[i] += [0 for _ in range(max_len - len(graph[i]))]
                if max_len > 100 :
                    graph[i] = graph[i][:100]
            # 2-5. C 연산의 경우 원상복구
            if col : graph = list(zip(*graph))
            # 2-6. (r, c)에 k값이 있는 경우
            if r <= len(graph) and c <= len(graph[0]) and graph[r-1][c-1] == k :
                print(ans)
                break
        # 3. -1 출력
        else : print(-1)

if __name__ == "__main__":
    r, c, k = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(3)]
    solution(r, c, k, graph)