[백준] 17406번 파이썬 - 배열 돌리기 4

백준 17406

 

배열이 주어지고 시계 방향으로 회전 시킬 범위 r,c,s가 주어진다.

주어진 범위대로 배열을 돌리면 되는데, 회전 연산들의 순서에 따라 배열 A의 크기가 달라진다.

 

나는 배열 A의 크기를 구하는 countLine 함수와

주어진 범위대로 배열을 회전시키는 rotateArray 함수를 만들어 주었다.

(배열을 회전 시키는 것은 배열 돌리기 문제 1,2,3 을 통해 해보아서 비교적 쉽게 구현할 수 있었다.)

 

회전 연산의 순서를 섞어 배열 A의 최솟값을 구하는 것에서 많이 고민했는데 

문제의 범위 제한은 다음과 같았다.

K의 범위가 최대 6이기 때문에 permutations를 써도 될 것 같았고 

(permutations의 시간 복잡도는 n!/r!)

permu라는 리스트에 순열 값을 저장하여 최솟값을 계산하였다.

 

제출후 결과는 실패였다..

 

왜?

반례를 찾을 수가 없어서 애를 먹었다.

당연했다. 거기서 틀린게 아니었으니까.. 아래 코드를 보자.

for i in permu:
    for j in i:
        r,c,s = j
        rotateArray(array,r,c,s) # array가 돌려진 상태로 갱신되어버림
    ans = min(ans,countLine(array))

 

이렇게 코드를 짜게 되면 4번째 줄에서 주어진 r,c,s 값대로 회전되어진 array가 반환된다.

permu 안의 다른 i값으로 계산할 때 초기 array값이 아닌 회전되어진 array값이 계산되어 버리는 것이다.

그렇다면 새로운 리스트에 array값을 넣어서 계산해주어야 한다.

 

 

※

arr =  array와 같이 사용하는 것을 '얕은 복사' 라고 한다.

이 얕은 복사는 언뜻 보기에는 arr라는 리스트에 array라는 값을 집어 넣었기 때문에 별도의 값이 새로 생성된 것 처럼 보인다.

하지만 이렇게 복사하게 되면 arr와 array의 값과 주소는 같은 곳을 참조하게 된다.

(ex) arr.append([3,4,2]) 를 하게 되면 array에도 같은 값이 append 된다.

 

17406 문제에서 이렇게 얕은 복사를 사용하게 되면 회전되어진 array가 반환되는 동일한 문제가 발생할 것이다. 

 

그렇다면?

이 문제를 해결하기 위해 파이썬의 copy 모듈의 deepcopy 함수를 사용하였다.

import copy

for i in permu:
    arr = copy.deepcopy(array)
    for j in i:
        r,c,s = j
        rotateArray(arr,r,c,s)
    ans = min(ans,countLine(arr))

 

깊은 복사는 내부에 있는 객체 모두 새롭게 만들어주는 작업을 한다.

그냥 독립적인 새로운 리스트가 생성되는 것이다.

이 깊은 복사를 사용하여 새로운 리스트 arr를 생성하니 문제가 해결되었다.

 

코드

from itertools import permutations
import copy
import sys
input = sys.stdin.readline

def countLine(array):
    minSum = int(1e9)
    for i in array:
        minSum = min(minSum,sum(i))
    return minSum

def rotateArray(array,r,c,s):
    x,y,a,b = r-s-1,c-s-1,r+s-1,c+s-1

    for i in range(min((a-x),(b-y))//2):
        nx,ny,mx,my = x+i,y+i,a-i,b-i       
        value = array[nx][ny]

        # 위
        for j in range(ny+1,my+1):
            tmp = array[nx][j]
            array[nx][j] = value
            value = tmp
        
        # 오른쪽
        for j in range(nx+1,mx+1):
            tmp = array[j][my]
            array[j][my] = value
            value = tmp

        # 아래
        for j in range(my-1,ny-1,-1):
            tmp = array[mx][j]
            array[mx][j] = value
            value = tmp
        
        # 왼쪽
        for j in range(mx,nx,-1):
            tmp = array[j-1][ny]
            array[j-1][ny] = value
            value = tmp

    return array

n,m,k = map(int,input().split())
array = []
for _ in range(n):
    array.append(list(map(int,input().split())))

krr = []
for _ in range(k):
    r,c,s = map(int,input().split())
    krr.append([r,c,s])

permu = list(permutations(krr,len(krr)))

ans = int(1e9)
for i in permu:
    arr = copy.deepcopy(array)
    for j in i:
        r,c,s = j
        rotateArray(arr,r,c,s)
    ans = min(ans,countLine(arr))

print(ans)

 

 

 

 

17406번: 배열 돌리기 4