새로 알게된 것
- 배열에 다른 배열이름을 참조하면, 주소 복사가 되어 얕은 복사가 되어버림
제출 코드
- 배열돌리기 1과 비슷하게, 리스트와 순열 사용 (+Map 추가 사용)
- 3시간 반 정도 소요
- 인덱스 값 계산 과정에서 조금씩 실수해서, 여러번 인덱스범위에러 남
- 제대로 수행된 후 값이 이상했던 이유 → 회전 진행하면서 전달한 배열이 얕은복사가 되어, 원본 배열을 훼손하고 있었다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class G17406_turnArray4 {
static int R, N ,M;
static int minSum = Integer.MAX_VALUE;
static int[] di = {0, 1, 0, -1}; // shift : right-down-left-up
static int[] dj = {1, 0 ,-1, 0};
static boolean[] selected;
static int[] order;
static int[][] arr, rotate;
static Map<Integer, List> queue = new HashMap<>();
/* 회전 연산 수행 메소드
* - arr : 회전할 배열
* - idx : 수행될 회전 연산 번호
*/
static int[][] rotateArr(int [][] arr, int idx) {
if(idx == R) return arr;
int r = order[idx]; //연산인덱스
int[][] result = new int[N][M]; // 회전할 배열 깊은복사
for(int n=0; n<N; n++) {
for(int m=0; m<M; m++) {
result[n][m] = arr[n][m];
}
}
int now_i = rotate[r][0]-1;
int now_j = rotate[r][1]-1;
for(int i=1; i<=rotate[r][2]; i++) { // 중심에서부터 한 사이클씩 회전
now_i--;
now_j--;
int tmp_i = now_i;
int tmp_j = now_j;
List<Integer> qu = queue.get(i);
int size = qu.size();
for(int q=0; q<size; q++) { // 사이클 내부 하나씩 이동
result[tmp_i+di[qu.get(q)]][tmp_j+dj[qu.get(q)]] = arr[tmp_i][tmp_j];
tmp_i += di[qu.get(q)];
tmp_j += dj[qu.get(q)];
}
}
return rotateArr(result, ++idx);
}
/* 행의 최소합 계산 메소드
* - 회전연산이 끝난 배열의 최소합을 계산
*/
static void calcSum() {
int[][] result = rotateArr(arr, 0);
for(int n=0; n<N; n++) {
int sum=0;
for(int m=0; m<M; m++) {
sum+=result[n][m];
}
minSum = Math.min(minSum, sum);
}
}
/* 회전 연산 순열 생성 메소드
* n - 순열 인덱스
*/
static void perm(int n) {
if(n==R) {
calcSum();
return;
}
for(int r=0; r<R; r++) {
if(!selected[r]) {
selected[r] = true;
order[n] = r;
perm(n+1);
selected[r] = false;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 입력
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]);
M = Integer.parseInt(line[1]);
R = Integer.parseInt(line[2]);
arr = new int[N][M];
for(int n=0; n<N; n++) {
arr[n] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
rotate = new int[R][3];
int max_r = Integer.MIN_VALUE;
for(int r=0; r<R; r++) {
rotate[r] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
max_r = Math.max(max_r, rotate[r][2]);
}
// 2. 사이클 큐 모두 만들어놓기
for(int i=1; i<=max_r; i++) {
List<Integer> list = new ArrayList<>();
for(int d=0; d<4; d++) {
for(int j=0; j<i*2; j++) {
list.add(d);
}
}
queue.put(i, list);
}
// 3. 회전 수행 후 결과 출력
selected = new boolean[R];
order = new int[R];
perm(0);
System.out.println(minSum);
}
}