17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
앞의 배열 돌리기1, 2와 같이 배열이 주어지고 이 문제는 회전시킬 구간이 추가로 주어집니다.
구간은 r c s 이렇게 들어오는데 구간 (r - s, c - s) ~ (r + s, c + s)를 1번 회전시켜라는 뜻입니다.
하지만 이 연산 순서를 임의로 정해서 배열 A의 값을 최소로 해야하는 문제입니다.
즉, 구간정보를 브루트포스방식을 사용하여 모든 순서로 연산을 다 해봐야합니다.
연산 순서는 ArrayList를 활용하여 구간을 넣었다 뺐다 하는 방식으로 정하였고, 순서를 모두 정하면 list의 값을 복사한 다른 배열을 선언하여 모든 회전을 수행한 후에 A의 최솟값을 구하였습니다.
회전 로직은 1번, 2번과 같지만 구간에 해당하는 숫자가 1개인 경우 next로 자신으로 설정하는 예외처리를 해주었습니다.
|
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
134
135
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int direct[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
static ArrayList<int[]> rotate = new ArrayList<>();
static ArrayList<int[]> rotatesolve = new ArrayList<>();
static boolean visit[][], chk[];
static int list[][], clist[][];
static int N, M, K, r, c, s;
static int sx, sy, ex, ey, ans = Integer.MAX_VALUE;
static void print() {
System.out.println(ans);
}
static int dfs(int x, int y, int idx) {
visit[x][y] = true;
int nx = x + direct[idx][0];
int ny = y + direct[idx][1];
if (nx < sx || ny < sy || nx > ex || ny > ey) {
idx++;
nx = x + direct[idx][0];
ny = y + direct[idx][1];
if (nx < sx || ny < sy || nx > ex || ny > ey) {
nx = x;
ny = y;
}
}
if (visit[nx][ny]) {
int tmp = clist[x][y];
clist[x][y] = clist[nx][ny];
return tmp;
}
int tmp = clist[x][y];
clist[x][y] = dfs(nx, ny, idx);
return tmp;
}
static void solve(int rr, int cc, int ss) {
sx = rr - ss;
sy = cc - ss;
ex = rr + ss;
ey = cc + ss;
for (int i = 0;; i++) {
dfs(sx, sy, 0);
sx++;
sy++;
ex--;
ey--;
if (sx > ex || sy > ey)
break;
}
for (int i = rr - ss; i <= rr + ss; i++) {
Arrays.fill(visit[i], false);
}
}
static void func(int cnt) {
if (cnt == K) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
clist[i][j] = list[i][j];
}
for (int i = 0; i < K; i++) {
solve(rotatesolve.get(i)[0], rotatesolve.get(i)[1], rotatesolve.get(i)[2]);
}
for (int i = 1; i <= N; i++) {
int sum = 0;
for (int j = 1; j <= M; j++) {
sum += clist[i][j];
}
ans = Math.min(ans, sum);
}
return;
}
for (int i = 0; i < K; i++) {
if (chk[i])
continue;
rotatesolve.add(rotate.get(i));
chk[i] = true;
func(cnt + 1);
chk[i] = false;
rotatesolve.remove(cnt);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
list = new int[N + 1][M + 1];
clist = new int[N + 1][M + 1];
visit = new boolean[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
rotate.add(new int[] { r, c, s });
}
chk = new boolean[K];
}
public static void main(String[] args) throws Exception {
input();
func(0);
print();
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 1987 알파벳 (0) | 2021.02.18 |
|---|---|
| boj 3109 빵집 (0) | 2021.02.18 |
| boj 16927 배열 돌리기 2 (0) | 2021.02.10 |
| boj 16926 배열 돌리기 1 (0) | 2021.02.10 |
| boj 1068 트리 (0) | 2021.02.09 |