여기서 사용했던 핵심 포인트는 조합을 사용해서 회전 연산의 순서를 결정하고, 그 것을 바탕으로 해당 위치에 대한 배열을 돌려야 한다.
1. 먼저 조합을 구해야 한다. ---> 주어진 예시는 (3, 4, 2), (4, 2, 1)일 때, 첫 번째 회전 방법은 (3, 4, 2) -> (4, 2, 1)이 방법일 것이고, 두 번째 방법은 (4, 2, 1) -> (3, 4, 2)의 순서를 통해 배열을 회전시켜야 한다. ---> 조합을 통해 위 순서에 대한 조합을 구한다. (combination)
2. 조합의 결과를 통해서 해당 위치에 대한 회전을 한다. ---> 다양한 회전 순서 조합에 대한 경우의 수가 나오므로 조합 연산 1개가 완성되면 기존의 2차원 배열을 깊은 복사를 통해 다른 경우의 수에서 배열을 회전할 때, 이전에 했던 배열 돌리는 경우의 연산과 영향이 가지 않도로 한다. ---> 배열 돌리기는 각 꼭지점을 기준으로 while문을 돌리다가 한 사이클이 끝나면 각 꼭지점의 위치를 점점 좁혀나간다.
---> 꼭지점의 위치를 줄여나가다가 각 꼭지점의 차이가 1 미만일 경우 while문을 종료하도록 한다. (java에서 구현함)
3. 배열을 돌렸으면 각 행의 합을 구하고, 그 중 최솟값을 찾는다.
2. 정답코드 Python
import sys
input = sys.stdin.readline
from itertools import permutations
from copy import deepcopy
N, M, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
k_list = [list(map(int, input().split())) for _ in range(K)]
min_v = sys.maxsize
def dfs(idx):
global min_v, graph
maps = graph
for perm in permutations(k_list, K):
maps = deepcopy(graph)
for nr, nc, es in perm:
for ns in range(es, 0, -1):
start, end = [nr - ns - 1, nc - ns - 1], [nr + ns - 1, nc + ns - 1]
temp_1 = maps[start[0]][start[1]]
for i in range(start[1] + 1, end[1] + 1):
temp_2 = maps[start[0]][i]
maps[start[0]][i] = temp_1
temp_1 = temp_2
for i in range(start[0] + 1, end[0] + 1):
temp_2 = maps[i][end[1]]
maps[i][end[1]] = temp_1
temp_1 = temp_2
for i in range(end[1] - 1, start[1] - 1, -1):
temp_2 = maps[end[0]][i]
maps[end[0]][i] = temp_1
temp_1 = temp_2
for i in range(end[0] - 1, start[0] - 1, -1):
temp_2 = maps[i][start[1]]
maps[i][start[1]] = temp_1
temp_1 = temp_2
for row in maps:
min_v = min(min_v, sum(row))
dfs(0)
print(min_v)
3. 정답코드 Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, K, answer;
static int minV;
static int[][] maps, new_maps;
static int[][] R;
static int[] target;
static boolean[] chk;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
maps = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
}
}
R = new int[K][3];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
R[i][0] = Integer.parseInt(st.nextToken());
R[i][1] = Integer.parseInt(st.nextToken());
R[i][2] = Integer.parseInt(st.nextToken());
}
target = new int[K];
chk = new boolean[K];
answer = Integer.MAX_VALUE;
dfs(0);
System.out.println(answer);
}
static void dfs(int idx) {
if (idx == K) {
// 2차원 배열 복사
int[][] new_maps = new int[N][M];
for (int i = 0; i < N; i++) {
new_maps[i] = maps[i].clone();
}
int[] check = new int[3];
for (int j = 0; j < K; j++) {
for (int k = 0; k < 3; k++) {
check[k] = R[target[j]][k];
}
rotate(check[0], check[1], check[2], new_maps);
}
for (int r = 0; r < N; r++) {
int sum = 0;
for (int c = 0; c < M; c++) {
sum += new_maps[r][c];
}
answer = Math.min(answer, sum);
}
return;
}
for (int i = 0; i < K; i++) {
if (chk[i]) continue;
target[idx] = i;
chk[i] = true;
dfs(idx + 1);
chk[i] = false;
}
}
static void rotate(int r, int c, int s, int[][] new_maps) {
int y1 = r - s - 1;
int x1 = c - s - 1;
int y2 = r + s - 1;
int x2 = c + s - 1;
// 회전 시작
while (true) {
// 종료 조건
if (Math.abs(y1 - y2) < 1 && Math.abs(x1 - x2) < 1) return;
int temp = new_maps[y1][x2];
// 위쪽
for (int i = x2; i > x1; i--) {
new_maps[y1][i] = new_maps[y1][i - 1];
}
// 왼쪽
for (int i = y1; i < y2; i++) {
new_maps[i][x1] = new_maps[i + 1][x1];
}
// 아래쪽
for (int i = x1; i < x2; i++) {
new_maps[y2][i] = new_maps[y2][i + 1];
}
// 오른쪽
for (int i = y2; i > y1; i--) {
new_maps[i][x2] = new_maps[i - 1][x2];
}
new_maps[y1 + 1][x2] = temp;
y1++;
x1++;
y2--;
x2--;
}
}
}
