JUST WRITE IT. HomeArchivesTagsCategories
백준 17406번 배열 돌리기 4
|AlgorithmBOJ|

#17406. 배열 돌리기 4

Problem

Solution

  • 회전 연산 순서를 정한다. (0, 1, 2) 와 (1, 0, 2)는 다른 순서이다!
  • 가장 바깥쪽 부터 시계방향으로 각 원소들을 회전시킨다.
    가장 바깥쪽 크기는 2*s+1이다.
  • 시작 지점부터 시작해서 +1씩, 크기는 -2씩 변경하며 회전시킨다.
  • 중앙 지점으 만나면 더이상 회전시킬 수 없으므로 종료한다.
  • 회전은 아래와 같은 방법으로 진행한다.
  • “미세먼지 안녕!” 문제에서 설명한 배열 회전 방법과 동일하다.
    여기선 시계방향이므로 2번째 그림이 이에 해당한다.

1 Try

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
#include <iostream>
using namespace std;
int N, M, K, ans = 1e9;
int arr[50][50];
int copy_arr[50][50];
int order[6];
bool selected[6];
struct Inst {
	int r, c, s;
}ins[6];
void CopyArray() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			copy_arr[i][j] = arr[i][j];
		}
	}
}
int getSum() {
	int res = 1e9;
	for (int i = 0; i < N; ++i) {
		int sum = 0;
		for (int j = 0; j < M; ++j) {
			sum += copy_arr[i][j];
		}
		if (res > sum) res = sum;
	}
	return res;
}
void Rotate() {
	CopyArray();
	for (int i = 0; i < K; ++i) {
		int len = ins[order[i]].s * 2 + 1; // 가장 바깥쪽 크기
		int mid_r = ins[order[i]].r; // 중심 좌표
		int mid_c = ins[order[i]].c;
		int start_r = ins[order[i]].r - ins[order[i]].s; // 시작 좌표
		int start_c = ins[order[i]].c - ins[order[i]].s;
		while (true) {
			if (mid_r == start_r && mid_c == start_c) break; // 중심점이면 종료
			int temp = copy_arr[start_r][start_c]; // 시작지점 값만 빼놓기
			int end_r = start_r + len - 1; // 끝 행
			int end_c = start_c + len - 1; // 끝 열
			for (int r = start_r; r < start_r + len - 1; ++r) { // (1)
				copy_arr[r][start_c] = copy_arr[r + 1][start_c];
			}
			for (int c = start_c; c < start_c + len - 1; ++c) { // (2)
				copy_arr[end_r][c] = copy_arr[end_r][c + 1];
			}
			for (int r = end_r; r > start_r; --r) { // (3)
				copy_arr[r][end_c] = copy_arr[r - 1][end_c];
			}
			for (int c = end_c; c > start_c + 1; --c) { // (4)
				copy_arr[start_r][c] = copy_arr[start_r][c - 1];
			}
			copy_arr[start_r][start_c + 1] = temp; // 빼놓은 값 넣기
			start_r++; start_c++; len -= 2; // 시작지점 및 길이 갱신
		}
	}
	int res = getSum();
	if (ans > res) ans = res;
}
void SelectOrder(int cnt) {
	if (cnt == K) {
		Rotate();
		return;
	}
	for (int i = 0; i < K; ++i) {
		if (selected[i]) continue;
		order[cnt] = i;
		selected[i] = true;
		SelectOrder(cnt + 1);
		selected[i] = false;
	}
}
int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < K; ++i) {
		int r, c, s;
		cin >> r >> c >> s;
		ins[i] = { r-1, c-1, s };
	}
	SelectOrder(0);
	cout << ans << "\n";
	return 0;
}
Algorithm