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

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

17406번: 배열 돌리기 4

 

 

 

# 조건

• 크기가 NxM 크기인 배열 A
• 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미
• 배열은 회전 연산을 수행할 수 있는데 회전 연산은 (r,c,s) 세 정수로 이루어져있다.
• 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아래 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미
• 예 - 회전 연산 (3,4,2)

• 회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다
• 회전 연산의 순서는 임의로 정해도 되지만, 모두 한 번씩 사용해야 한다.

 

# 접근 방법

• 우선 순열을 이용하여 회전 연산 순서를 정해준다.
• 또한 인덱스는 0부터 시작이지만 배열은 1부터 시작이기 때문에, 회전 연산을 할 때 -1을 해주어야 한다.
• 각 위치에 따라 받아오는 값을 달리해주며 배열을 회전시켜준다.
• 회전 연산을 여러 번해야되는 경우가 있으므로 deepcopy를 이용하여 복사시켜준다.
• 또한 다른 순열을 들어가기전 전부 초기 배열로 완성시켜준다.

위 방법으로 하니 pypy만 통과

• 파이썬을 잘 이용하지 못한 코드였다.
• 파이썬의 slicing 기능을 이용하여 각 라인의 규칙에 따라 한칸씩 밀어주면 된다.
• 처음 밀고 나면 시작하는 칸이 비게 되므로 다음은 위쪽으로 밀어주고, 왼쪽으로 밀어주고, 아래로 밀어준다.
• 또한 밀고 나면 5번의 정보가 손실되므로 처음에 저장해주기

 

• 마지막 결과가 이렇게 되므로 4번을 -> 5번으로 바꿔준다면 완료

 

 

# pypy 통과 코드 - 인덱스와 규칙 활용

import sys  
sys.stdin = open('input.txt')  
from copy import deepcopy  
from itertools import permutations  
input = sys.stdin.readline  
  
N, M, K = map(int, input().split())  
arr1 = [[*map(int, input().split())] for _ in range(N)]  
rotate = [[*map(int, input().split())] for _ in range(K)]  
  
# 회전 연산 순서 순열  
order = list(permutations(rotate, K))  
  
# 결과저장 배열  
result = [[0]*M for _ in range(N)]  
# 최소값 저장  
cnt = float('inf')  
  
# 순열 길이만큼 반복  
for k in range(len(order)):  
    # 초기 배열로 돌아가기  
    arr = deepcopy(arr1)  
    result = deepcopy(arr)  
    # K개의 회전 배열만큼 반복  
    for l in range(K):  
  
        sti = order[k][l][0] - order[k][l][2] - 1  
        stj = order[k][l][1] - order[k][l][2] - 1  
        endi = order[k][l][0] + order[k][l][2] - 1  
        endj = order[k][l][1] + order[k][l][2] - 1  
        # 내부 반복 위한 while문  
        while sti <= endi and stj <= endj:  
            # 회전 시켜줄 네모부터 반복  
            for i in range(sti, endi+1):  
                for j in range(stj, endj+1):  
                    # 시작 행과 행이 같다면 좌 -> 우  
                    # 첫 시작점은 밑에서 들고와야되서 배제 해주기                    
                    if i == sti and j != stj:  
                        result[i][j] = arr[i][j-1]  
                    # 종료 열과 열이 같다면 위에서 아래  
                    elif j == endj and i != sti:  
                        result[i][j] = arr[i-1][j]  
                    # 종료 행과 같다면 우 -> 좌  
                    elif i == endi and j != endj:  
                        result[i][j] = arr[i][j+1]  
                    # 시작열과 같다면 하 -> 상  
                    elif j == stj and i != endi:  
                        result[i][j] = arr[i+1][j]  
  
            # 다 채워줬다면 내부로 들어가기  
            sti += 1  
            stj += 1  
            endi -= 1  
            endj -= 1  
  
        # 여러 번 회전 위한 배열 deepcopy  
        arr = deepcopy(result)  
  
    # 최소값 구해주기  
    for b in result:  
        cnt2 = sum(b)  
        if cnt2 < cnt:  
            cnt = cnt2  
    # print(result)  
  
print(cnt)

 

 

# python 통과 - slicing 이용

 

import sys  
sys.stdin = open('input.txt')  
from copy import deepcopy  
from itertools import permutations  
input = sys.stdin.readline  
  
N, M, K = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  
rotate = [[*map(int, input().split())] for _ in range(K)]  
cnt = float('inf')  
  
# 순열 길이만큼 반복  
for b in permutations(rotate, K):  
    result = deepcopy(arr)  
    # 회전 배열 인자 받아주기  
    for r,c,s in b:  
        # 인덱스이므로 -1  
        r -= 1  
        c -= 1  
        # 내부로 들어갈 수록 s가 1씩 줄어든다.  
        # 즉, 작은 네모를 회전 시키는 것        
        for n in range(s, 0, -1):  
            # 5번 칸의 정보가 날아가므로 미리 저장해주기  
            tmp = result[r-n][c+n]  
  
            # 사각형 윗 변 오른쪽으로 슬라이싱  
            result[r - n][c - n + 1:c + n + 1] = result[r - n][c - n:c + n]  
  
            # 슬라이싱하고 나면 처음 시작 칸이 빈다  
            # 따라서 채워주기 위해서 위쪽 슬라이싱 진행            
            # 사각형 왼쪽 변 위로 슬라이싱            
            # 위에서부터 해주어야 값이 제대로 갱신됨            
            for j in range(r - n, r + n):  
                result[j][c - n] = result[j + 1][c - n]  
  
            # 사각형 아랫 변 왼쪽으로 슬라이싱  
            result[r+n][c-n:c+n] = result[r+n][c-n+1:c+n+1]  
  
            # 사각형 오른쪽 변 아래쪽으로 슬라이싱  
            # 아래에서 부터 해주어야 값이 제대로 갱신            
            for i in range(r + n, r - n, -1):  
                result[i][c + n] = result[i - 1][c + n]  
  
            # 비어있는 5번칸 채워주기  
            result[r-n+1][c+n] = tmp  
  
    # 최소값 찾기  
    for i in result:  
        if sum(i) < cnt:  
            cnt = sum(i)  
  
print(cnt)