[문제 바로가기] https://www.acmicpc.net/problem/17406
📌문제 설명
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.제한
- 3 ≤ N, M ≤ 50
- 1 ≤ K ≤ 6
- 1 ≤ A[i][j] ≤ 100
- 1 ≤ s
- 1 ≤ r-s < r < r+s ≤ N
- 1 ≤ c-s < c < c+s ≤ M
💡 문제 풀이
'배열의 회전' 구현을 제외하고는 별다른 어려움이 없었던 문제였다.
step 1)
입력값을 받는다. (백준에서는 sys.stdin.readline()으로 받자...)
- matrix : 배열 A
- rotates : 회전 연산의 정보(r, c, s)를 담는 배열
- answer : 회전 연산을 마친 후 배열 A의 값의 최소값을 담는 변수
step 2)
회전 연산의 순서에 따라 배열 A의 값이 달라질 수 있다.
따라서, permutation(순열)을 이용하여 가능한 모든 회전 연산의 경우에 대해 따져본다.
이 때, matrix(배열 A)를 직접 회전시켜야 하기 때문에
deepcopy를 이용하여 원본 배열을 복사한 값을 넣어준다.
step 3)
순열을 이용하여 회전 연산의 순서를 정했다면, 배열 A를 회전시켜 원하는 값을 찾는다.
회전 연산의 구현은 다음과 같이 진행하였다.
회전 연산이 달팽이 모양처럼 내부까지 회전이 되는 것이 아니라 겉에서 부터 안쪽까지 한 줄씩 사각형의 형태로 회전이 진행된다.
이 때, s의 값이 곧 회전을 돌리야하는 사각형의 개수를 의미하기 때문에 s의 값과 배열의 인덱스를 잘 활용하면 회전 연산을 구현할 수 있다.
사각형 형태의 회전이므로 '상, 하, 좌, 우' 4개의 회전에 대한 반복문을 따로 만들어서 구현하였다.
회전연산을 진행할 경우 가장 신경써줘야 하는 부분이 'index out of range'를 발생시키는 사각형의 꼭짓점 부분인데
해당 값들을 변수에 담아둔 후 회전 연산을 마친다음 들어가야 할 인덱스에 직접 넣어주었다.
- top_right : 우측상단 지점의 값
- bottom_left : 좌측하단 지점의 값
- bottom_right : 우측하단 지점의 값
step 4)
회전 연산을 모두 마친 배열은 반복문을 이용하여 '배열 값의 최소값'을 answer에 최신화 시켜준다.
코드는 아래와 같다.
import sys
from itertools import permutations
from copy import deepcopy
def rotate(cases, copy_matrix):
global answer
for case in cases:
r, c, s = case
r -= 1
c -= 1
print(r, c, s)
for inner in range(s, 0, -1):
top_right = copy_matrix[r-inner][c+inner]
bottom_left = copy_matrix[r+inner][c-inner]
bottom_right = copy_matrix[r+inner][c+inner]
for idx in range(c+inner, c-inner, -1):
copy_matrix[r-inner][idx] = copy_matrix[r-inner][idx-1]
for idx in range(r+inner, r-inner, -1):
copy_matrix[idx][c+inner] = copy_matrix[idx-1][c+inner]
for idx in range(c-inner, c+inner):
copy_matrix[r+inner][idx] = copy_matrix[r+inner][idx+1]
for idx in range(r-inner, r+inner):
copy_matrix[idx][c-inner] = copy_matrix[idx+1][c-inner]
copy_matrix[r-inner+1][c+inner] = top_right
copy_matrix[r+inner][c+inner-1] = bottom_right
copy_matrix[r+inner-1][c-inner] = bottom_left
for row in copy_matrix:
answer = min(answer, sum(row))
N, M, K = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
rotates = [list(map(int, sys.stdin.readline().split())) for _ in range(K)]
answer = 0xfffffffffffff
for cases in permutations(rotates, K):
rotate(cases, deepcopy(matrix))
print(answer)
이번문제는 Python3까지 통과하였다. 😊
