💡 문제
크기가 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
💭 접근
이 문제는 조금 까다로운 구현이 섞인 순열 문제이다.
회전 연산을 수행하는 순서에 따라 배열의 형태가 달라지므로, 입력으로 주어진 회전 연산들의 순열을 구한 뒤, 이에 대하여 회전 연산을 수행하고 정답을 구하면 된다.
먼저, 입력으로 주어진 회전 연산들의 순열을 구한다.
def dfs(depth):
if depth == k:
rotate()
return
for i in range(k):
if i not in tmp:
tmp.append(i)
dfs(depth + 1)
tmp.pop()이후, 하나의 순열이 완성되면 이를 배열에 적용하고 정답을 갱신한다. 이는 rotate() 함수로 구현하였다.
def rotate():
global ans
tmp_graph = [graph[i][:] for i in range(n)]
for idx in tmp:
r, c, s = coord[idx]
for i in range(1, s + 1):
prev_num = tmp_graph[r - i + 1][c - i]
for j in range(c - i, c + i + 1):
curr_num = tmp_graph[r - i][j]
tmp_graph[r - i][j] = prev_num
prev_num = curr_num
for j in range(r - i + 1, r + i + 1):
curr_num = tmp_graph[j][c + i]
tmp_graph[j][c + i] = prev_num
prev_num = curr_num
for j in range(c + i - 1, c - i - 1, -1):
curr_num = tmp_graph[r + i][j]
tmp_graph[r + i][j] = prev_num
prev_num = curr_num
for j in range(r + i - 1, r - i, -1):
curr_num = tmp_graph[j][c - i]
tmp_graph[j][c - i] = prev_num
prev_num = curr_num
for i in range(n):
ans = min(ans, sum(tmp_graph[i]))이처럼 회전 연산의 순서를 적절히 섞어 모든 순열에 대해 정답을 비교한 뒤, 최솟값을 구하면 된다.
📒 코드
def dfs(depth):
if depth == k:
rotate()
return
for i in range(k):
if i not in tmp:
tmp.append(i)
dfs(depth + 1)
tmp.pop()
def rotate():
global ans
tmp_graph = [graph[i][:] for i in range(n)]
for idx in tmp:
r, c, s = coord[idx]
for i in range(1, s + 1):
prev_num = tmp_graph[r - i + 1][c - i]
for j in range(c - i, c + i + 1):
curr_num = tmp_graph[r - i][j]
tmp_graph[r - i][j] = prev_num
prev_num = curr_num
for j in range(r - i + 1, r + i + 1):
curr_num = tmp_graph[j][c + i]
tmp_graph[j][c + i] = prev_num
prev_num = curr_num
for j in range(c + i - 1, c - i - 1, -1):
curr_num = tmp_graph[r + i][j]
tmp_graph[r + i][j] = prev_num
prev_num = curr_num
for j in range(r + i - 1, r - i, -1):
curr_num = tmp_graph[j][c - i]
tmp_graph[j][c - i] = prev_num
prev_num = curr_num
for i in range(n):
ans = min(ans, sum(tmp_graph[i]))
n, m, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
coord = []
for _ in range(k):
r, c, s = map(int, input().split())
coord.append([r - 1, c - 1, s])
ans = float('inf')
tmp = []
dfs(0)
print(ans)💭 후기
문제 풀이의 방향은 쉽게 잡을 수 있었지만 회전 연산을 수행하는 과정에서 실수를 많이 하여 까다로웠던 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/17406
