백준 17140번 이차원 배열과 연산 골드4 파이썬

1시간 10분 걸림. 문제 제대로 구현 안해서 한번 틀리고, 인덱스 에러를 안잡아 줘서 한번 틀렸고, 가짓수를 다 해봤는데 안될 경우를 생각하지 못해 여러번 틀렸다. 안될 경우를 대비해 answer 에 불가능이란 값을 default 로 줬어야하는 문제.

transpose 함수를 알게 되었다.

def transpose(graph):
    return list(map(list, zip(*graph)))

문제

크기가 3×3인 배열 A가 있다. 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을 출력한다.

구현

import collections
import copy
import sys

sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline


def iinput(): return int(input())


def lisinput(): return list(map(int, input().split()))


def dq(a):
    return collections.deque(a)


def minput(): return map(int, input().split())


def liinput(): return list(map(int, list(input())))


def addNode(a, b):
    return [a[0] + b[0], a[1] + b[1]]


def returnValue(graph, node):
    return graph[node[0]][node[1]]


def transpose(graph):
    return list(map(list, zip(*graph)))


if __name__ == '__main__':
    r, c, k = minput()
    A = []
    r -= 1
    c -= 1


    def command(curA):
        if len(curA) >= len(curA[0]):
            return commandR(curA)
        else:
            return commandC(curA)


    def commandR(curA):
        newA = copy.deepcopy(curA)
        maxRow = 0
        for i in range(len(newA)):
            r = dict(collections.Counter(newA[i]))
            r.pop(0, None)
            arrR = list(sorted(r.items(), key=(lambda x: (x[1], x[0]))))
            newA[i] = []
            for k in arrR:
                if len(newA[i]) >= 100:
                    break
                else:
                    newA[i] += k
            maxRow = max(len(newA[i]), maxRow)
        for i in range(len(newA)):
            diff = maxRow - len(newA[i])
            newA[i] += [0 for ll in range(diff)]
        return newA


    def commandC(curA):
        newA = copy.deepcopy(curA)
        newA = transpose(newA)
        newA = commandR(newA)
        newA = transpose(newA)
        return newA


    for i in range(3):
        A.append(lisinput())

    will_visit = [{"sec": 1, "result": command(copy.deepcopy(A))}]
    visited = [copy.deepcopy(A)]
    answer = -1
    if len(A) > r and len(A[r]) > c and A[r][c] == k:
        answer = 0
    else:
        while will_visit:
            travel = will_visit.pop()
            if travel["sec"] > 100:
                answer = -1
                break
            if len(travel["result"]) > r and len(travel["result"][r]) > c and travel["result"][r][c] == k:
                answer = travel["sec"]
                break
            else:
                cR = command(travel["result"])
                if cR not in visited:
                    visited.append(cR)
                    will_visit.append({"sec": travel["sec"] + 1, "result": cR})
    print(answer)