문제 설명
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3
2 1 1
4 5 6배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
↑ ↓
A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6]
↑ ↑ ↓ ↓
A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6]
↑ ↑ ↓ ↓
A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6]
↑ ↓
A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]
A[6][1] A[6][2] A[6][3] A[6][4] A[6][5] A[6][6]회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
1 8 2 3 2 5
3 2 3 7 2 6
8 4 5 1 1 3
3 3 1 1 4 5
9 2 1 4 3 1
1 8 2 3 2 5
3 2 3 7 2 6
3 8 4 1 1 3
9 3 5 1 4 5
2 1 1 4 3 1
배열 A (3, 4, 2) 연산 수행 후 (4, 2, 1) 연산 수행 후
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
1 2 3 2 5 6
3 8 7 2 1 3
3 8 2 1 4 5
9 4 3 1 1 1
3 2 5 1 4 3
1 8 2 3 2 5
3 8 2 7 2 6
3 4 3 1 1 3
9 2 1 1 4 5
3 5 1 4 3 1
배열 A (4, 2, 1) 연산 수행 후 (3, 4, 2) 연산 수행 후
배열 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
전체 코드
import copy
import sys
from itertools import permutations
sys.setrecursionlimit(10 ** 5)
n, m, k = list(map(int, input().split()))
arr = []
for i in range(n):
data = list(map(int, input().split()))
arr.append(data)
instructions = []
for i in range(k):
r, c, s = list(map(int, input().split()))
instructions.append((r, c, s))
def get_value_of_arr(array: list) -> int:
value = 987654321
for a in range(n):
row_value = 0
for b in range(m):
row_value += array[a][b]
value = min(value, row_value)
return value
def rotate_arr(array: list, instruction):
row, column, diff = instruction
left_top = [row - diff - 1, column - diff - 1]
right_bot = [row + diff - 1, column + diff - 1]
while (left_top[0] != right_bot[0]) and (left_top[1] != right_bot[1]):
temp_right_top = array[left_top[0]][right_bot[1]]
# 동쪽 방향 이동
y = right_bot[1]
while y > left_top[1]:
array[left_top[0]][y] = array[left_top[0]][y - 1]
y -= 1
temp_right_bot = array[right_bot[0]][right_bot[1]]
# 남쪽 방향 이동
x = right_bot[0]
while x > left_top[0]:
array[x][right_bot[1]] = array[x - 1][right_bot[1]]
x -= 1
array[x + 1][right_bot[1]] = temp_right_top
# 서쪽 방향 이동
temp_left_bot = array[right_bot[0]][left_top[1]]
y = left_top[1]
while y < right_bot[1]:
array[right_bot[0]][y] = array[right_bot[0]][y + 1]
y += 1
array[right_bot[0]][y - 1] = temp_right_bot
# 북쪽 이동
x = left_top[0]
while x < right_bot[0]:
array[x][left_top[1]] = array[x + 1][left_top[1]]
x += 1
array[x - 1][left_top[1]] = temp_left_bot
# 맨 왼쪽과 맨 오른쪽의 좌표를 각각 수정해줍니다.
left_top[0] += 1
left_top[1] += 1
right_bot[0] -= 1
right_bot[1] -= 1
answer = 987654321
perm = list(permutations(instructions, len(instructions)))
for p in perm:
temp_arr = copy.deepcopy(arr)
for elem in p:
rotate_arr(temp_arr, elem)
answer = min(answer, get_value_of_arr(temp_arr))
print(answer)
해설
1. 제일 바깥쪽 시계 방향 이동부터 구현한다.
먼저, 맨 왼쪽 맨위를 left_top, 맨 오른쪽 맨 아래를 right_bot이라 하자.
그리고 시계 방향이므로 동,남,서,북 순서로 이동시킨다.
이 때, 처음부터 전체를 시계 방향으로 이동시키는 것을 고려하게 되면
머리가 복잡하다.
따라서 제일 바깥쪽 부분의 시계 방향 이동만 먼저 구현하자.
temp_right_top = array[left_top[0]][right_bot[1]]
# 동쪽 방향 이동
y = right_bot[1]
while y > left_top[1]:
array[left_top[0]][y] = array[left_top[0]][y - 1]
y -= 1
temp_right_bot = array[right_bot[0]][right_bot[1]]
# 남쪽 방향 이동
x = right_bot[0]
while x > left_top[0]:
array[x][right_bot[1]] = array[x - 1][right_bot[1]]
x -= 1
array[x + 1][right_bot[1]] = temp_right_top
# 서쪽 방향 이동
temp_left_bot = array[right_bot[0]][left_top[1]]
y = left_top[1]
while y < right_bot[1]:
array[right_bot[0]][y] = array[right_bot[0]][y + 1]
y += 1
array[right_bot[0]][y - 1] = temp_right_bot
# 북쪽 이동
x = left_top[0]
while x < right_bot[0]:
array[x][left_top[1]] = array[x + 1][left_top[1]]
x += 1
array[x - 1][left_top[1]] = temp_left_bot
2. 그 다음에는 공통 규칙을 적용하여 전체를 회전 시키자.
적용되는 사각형이 '정 사각형'이다.
그래서 제일 바깥 쪽 부분의 회전이 끝나면, 다음 바깥 쪽 부분의 회전을 해야 할 때 left_top 의 (x,y)좌표는 전부 + 1이 되고 right_bot의 (x,y)좌표는 전부 -1이 되어야 한다.
해당 좌표만 수정해주면 1.의 로직을 그대로 적용하여 다음 바깥 쪽 부분의 시계 방향 회전을 할 수 있다.
while (left_top[0] != right_bot[0]) and (left_top[1] != right_bot[1]):
...
# 맨 왼쪽과 맨 오른쪽의 좌표를 각각 수정해줍니다.
left_top[0] += 1
left_top[1] += 1
right_bot[0] -= 1
right_bot[1] -= 1
