배열 돌리기 4 - 파이썬

def permutation2(arr, length): #조합 [1,2,3],2 => [1,2],[1,3],[2,1],[2,3],[3,1],[3,2] 
    used = [0 for _ in range(len(arr))]
    returnArr = []
    def generate(chosen):
        if len(chosen) == length:
            returnArr.append(chosen[:])
            return
        for i in range(len(arr)):
            if used[i] == 0: #아직 사용 안됨
                used[i] = 1
                chosen.append(arr[i])
                generate(chosen)
                chosen.pop()
                used[i] = 0
    generate([])
    return returnArr

def rotate2(arr,case):
    returnSum = 2100000000
    tArr = copy.deepcopy(arr)
    for i in case:
        command = commands[i] #command = [3,4,2]
        for j in range(1,command[2]+1):
            arr = rotate_each(command[0]-1-j,command[1]-1-j,j*2+1,tArr)
    for tA in tArr:
        returnSum = min(returnSum,sum(tA))
        
    return returnSum
    
def rotate_each(x,y,d,arr):
    q = deque()
    for i in range(d-1):
        q.append(arr[x][y+i])
    for i in range(d-1):
        q.append(arr[x+i][y+d-1])
    for i in range(d-1):
        q.append(arr[x+d-1][y+d-1-i])
    for i in range(d-1):
        q.append(arr[x+d-1-i][y])
    q.rotate(1)
    for i in range(d-1):
        arr[x][y+i] = q.popleft()
    for i in range(d-1):
        arr[x+i][y+d-1] = q.popleft()
    for i in range(d-1):
        arr[x+d-1][y+d-1-i] = q.popleft()
    for i in range(d-1):
        arr[x + d - 1 - i][y] = q.popleft()
    return arr

N,M,K = map(int,input().split())
arrs = []
commands=[]

for _ in range(N):
    arrs.append(list(map(int,input().split())))
for _ in range(K):
    commands.append(list(map(int,input().split())))


case = [i for i in range(K)]
case = permutation2(case,K)

answer = 2100000000
for i in range(len(case)):
    #특정 경우의 명령 순서에서 총합
    tSum = rotate2(arrs,case[i])
    if answer > tSum:
        answer=tSum
print(answer)

두가지 단계로 나뉜다.

 

1. 명령의 조합을 구하기 위한 permutation() 함수 구현

2. 명령에서 수행할 배열 돌리기 구현

 

[1]의 경우 재귀함수를 이용해 간단히 구할 수 있음. combination 구하는 방법도 저 틀에서 벗어나지 않음

[2]의 경우 돌릴 2차원 배열을 껍질 단위로 deque에 저장하고 deque.rotate(1)로 회전 후 다시 순서대로 집어넣어주기만 하면 됨. 한번에 다 구현하면 힘드니 껍질별로 함수를 호출하는 형식으로 구현해줌.

 

 

 

문제를 잘못 이해해서 90도 회전인줄 알고 짠 90도 rotate 코드

def rotate(arr, case):
    tArr = copy.deepcopy(arr)

    for i in case:
        midX,midY,dist = commands[case[i]]
        startX = midX-1-dist
        startY = midY-1-dist
        tLen = 2*dist + 1
        for i in range(startX,startX+tLen):
            for j in range(startY,startY+tLen):
                print("i,j : ",i,j)
                convX = i - startX
                convY = j - startY
                print("convX, convY ",convX,convY)
                moveX = convY
                moveY = tLen - convX -1
                print("moveX, moveY : ",moveX,moveY)
                moveX += startX
                moveY += startY
                print("adjust moveX, moveY : ", moveX, moveY)
                print("=====================")
                tArr[moveX][moveY]=arr[i][j]

핵심은 두가지임.

1. [0,0]~[n,n]의 2차원 배열을 90도 시계방향으로 회전시키는 경우 arr[i][j] => arr[j][n-1-i]이 됨.

2. 돌리는 시점이 [0,0]부터 시작하지 않으니 [x,y] => [0,0] / rotate / [0,0] => [x,y]의 과정을 거쳐야함.